3
500 1000 1000
317580000000 363210000000
1 2 477339 100
2 3 917123 100
2 3 241406 32
3 4 969340 100
4 5 998848 100
4 5 182502 64
5 6 903090 100
6 7 996790 100
6 7 66120 20
6 7 22181 64
7 8 961032 100
7 8 318124 72
8 9 946275 100
8 9 26243 75
8 9 136552 50
9 10 945641 100
9 10 32454 43
10 11 952083 100
10 11 9865 90
10 11 18625 21
11 12 988172 100
12 13 957773 100
12 13 180641 55
13 14 917029 100
13 14 112469 41
13 14 863032 96
13 14 141720 42
14 15 994822 100
15 16 974744 100
15 16 57962 22
15 16 345602 88
15 16 35481 52
16 17 956721 100
17 18 987133 100
17 18 7452 6
17 18 137000 59
18 19 982245 100
19 20 914595 100
19 20 62652 34
20 21 982933 100
20 21 79886 66
20 21 217167 81
21 22 963796 100
22 23 965476 100
23 24 959842 100
23 24 17276 36
24 25 974934 100
25 26 989256 100
25 26 15429 30
26 27 980486 100
27 28 986287 100
27 28 161822 9
27 28 135193 85
28 29 957058 100
29 30 965257 100
30 31 912872 100
30 31 111519 23
31 32 990129 100
31 32 27938 10
32 33 950966 100
33 34 955157 100
33 34 86185 26
34 35 998738 100
34 35 227015 61
35 36 960470 100
36 37 982720 100
36 37 19841 27
37 38 971106 100
37 38 390059 70
38 39 949807 100
39 40 985038 100
39 40 43836 100
40 41 971328 100
40 41 56628 61
41 42 893527 100
42 43 990952 100
42 43 27280 2
43 44 856571 100
43 44 166910 62
43 44 163838 47
44 45 980309 100
45 46 851451 100
45 46 646787 92
45 46 424507 76
46 47 967660 100
47 48 987797 100
47 48 16996 16
48 49 987543 100
48 49 233160 7
48 49 285288 85
49 50 954795 100
49 50 79482 55
50 51 980065 100
50 51 16541 23
51 52 978395 100
51 52 133848 4
52 53 944326 100
52 53 271859 79
53 54 935862 100
54 55 922870 100
55 56 962776 100
55 56 56543 98
55 56 238676 14
56 57 939773 100
56 57 184813 69
57 58 998710 100
57 58 248127 33
58 59 986036 100
58 59 20150 70
59 60 943279 100
59 60 240364 84
60 61 995742 100
60 61 210198 71
60 61 395014 99
60 61 123613 17
61 62 898589 100
62 63 973860 100
62 63 75714 100
63 64 979427 100
63 64 129705 36
64 65 964762 100
64 65 24085 97
64 65 195515 29
65 66 971567 100
65 66 133480 43
65 66 302516 10
66 67 862911 100
67 68 867534 100
67 68 306498 99
68 69 998030 100
68 69 36557 92
69 70 967027 100
69 70 57949 83
70 71 963095 100
70 71 345 35
71 72 995710 100
71 72 50379 89
71 72 67231 36
71 72 7987 53
71 72 237179 91
71 72 192577 53
72 73 998443 100
73 74 866329 100
74 75 988710 100
75 76 790307 100
75 76 184197 85
75 76 135546 10
75 76 34692 14
76 77 877277 100
76 77 102235 89
77 78 942988 100
77 78 30932 90
78 79 991728 100
79 80 986319 100
79 80 100653 44
80 81 992905 100
81 82 971626 100
82 83 982173 100
82 83 441732 88
83 84 986577 100
83 84 28461 47
84 85 967614 100
85 86 997609 100
86 87 993140 100
87 88 959260 100
87 88 130220 56
88 89 925791 100
88 89 6033 40
89 90 996703 100
90 91 999232 100
90 91 388257 63
91 92 945184 100
91 92 96460 85
91 92 240774 93
91 92 6852 38
91 92 8988 52
92 93 978613 100
92 93 19129 11
93 94 995332 100
93 94 426004 86
93 94 534855 91
94 95 824686 100
94 95 7066 63
95 96 984452 100
96 97 910780 100
96 97 700789 87
97 98 988054 100
97 98 152678 12
97 98 61533 6
98 99 987827 100
98 99 160500 29
99 100 928572 100
99 100 57460 75
99 100 65990 99
100 101 907351 100
100 101 59954 13
100 101 157858 11
101 102 962934 100
101 102 88358 43
101 102 23915 2
102 103 988015 100
103 104 941526 100
103 104 87915 44
104 105 993010 100
104 105 4694 60
104 105 15826 80
105 106 917130 100
105 106 179876 93
106 107 921044 100
107 108 982468 100
108 109 995622 100
109 110 976610 100
109 110 175329 87
110 111 981155 100
110 111 59485 47
111 112 972252 100
112 113 997270 100
113 114 996778 100
113 114 194385 8
114 115 999120 100
114 115 563468 84
115 116 945481 100
116 117 998852 100
117 118 995178 100
118 119 988435 100
119 120 990743 100
119 120 112875 29
120 121 942229 100
120 121 257232 62
120 121 39613 12
120 121 57537 73
121 122 810675 100
122 123 961819 100
122 123 233045 45
122 123 43236 99
123 124 933116 100
123 124 282179 88
123 124 13928 6
124 125 970393 100
124 125 11399 47
125 126 970819 100
125 126 42094 23
126 127 968795 100
126 127 292675 65
127 128 881216 100
127 128 70334 29
127 128 35149 17
127 128 58500 68
128 129 968419 100
128 129 378049 43
129 130 983284 100
129 130 724796 48
130 131 847113 100
130 131 155024 36
130 131 140993 48
130 131 281307 61
131 132 991352 100
132 133 955054 100
132 133 1856 12
133 134 982627 100
134 135 907510 100
134 135 158559 71
135 136 923888 100
135 136 297627 76
135 136 124948 22
136 137 916412 100
136 137 9914 1
136 137 9740 69
137 138 993822 100
137 138 63720 14
138 139 999257 100
138 139 226451 99
138 139 197760 6
138 139 26666 15
139 140 986928 100
140 141 957729 100
140 141 259042 19
140 141 489117 83
141 142 960757 100
141 142 168740 82
142 143 999361 100
143 144 949778 100
144 145 988002 100
144 145 250193 35
144 145 59000 42
144 145 231272 50
145 146 907976 100
146 147 971866 100
146 147 39757 4
147 148 895344 100
148 149 923878 100
148 149 362699 46
149 150 918577 100
149 150 216932 60
150 151 975987 100
150 151 837831 97
151 152 897395 100
151 152 114665 33
152 153 995894 100
152 153 135772 40
153 154 944049 100
153 154 137616 60
154 155 890579 100
154 155 327844 41
155 156 974601 100
155 156 174444 51
155 156 84825 98
156 157 899209 100
157 158 985342 100
157 158 173958 39
158 159 998771 100
158 159 14530 57
158 159 139674 30
159 160 965598 100
159 160 713473 96
160 161 943666 100
161 162 970559 100
161 162 26648 68
161 162 41382 26
161 162 427843 99
162 163 967525 100
162 163 88670 5
163 164 995825 100
163 164 233615 84
163 164 108289 80
164 165 952823 100
164 165 107190 36
164 165 133350 7
165 166 916020 100
165 166 62052 56
166 167 879607 100
167 168 986174 100
167 168 347271 54
167 168 25233 22
168 169 824228 100
169 170 959432 100
169 170 364379 16
169 170 381704 76
169 170 189891 29
170 171 961226 100
170 171 159674 73
171 172 987336 100
172 173 928507 100
172 173 238234 3
173 174 962711 100
173 174 556232 73
173 174 24788 1
174 175 901562 100
175 176 955603 100
175 176 48762 77
176 177 919135 100
177 178 976702 100
177 178 183255 58
177 178 6292 87
178 179 917036 100
179 180 999190 100
179 180 7118 50
179 180 145447 28
180 181 995743 100
181 182 854022 100
182 183 978650 100
182 183 117745 46
182 183 312891 42
183 184 988596 100
183 184 92117 15
184 185 956157 100
184 185 460315 54
185 186 989151 100
185 186 138203 60
186 187 992277 100
186 187 148491 27
186 187 298609 41
186 187 97827 16
186 187 59730 53
187 188 977080 100
188 189 947240 100
188 189 186774 6
188 189 414695 91
189 190 976231 100
190 191 974920 100
190 191 445600 54
190 191 17130 43
191 192 961977 100
192 193 929462 100
192 193 169011 48
192 193 245234 4
193 194 943383 100
194 195 933893 100
194 195 362998 99
195 196 997946 100
195 196 403893 84
196 197 981401 100
197 198 939390 100
197 198 183417 22
198 199 996458 100
198 199 58522 64
199 200 960590 100
200 201 983856 100
200 201 379979 83
201 202 989588 100
202 203 961981 100
202 203 112350 57
203 204 849433 100
204 205 965896 100
204 205 87865 51
205 206 851566 100
205 206 34553 26
205 206 265392 30
206 207 923890 100
206 207 73344 46
207 208 978378 100
208 209 963553 100
209 210 980089 100
209 210 181671 56
209 210 123927 9
209 210 14848 12
210 211 988861 100
210 211 436185 29
210 211 52338 12
211 212 989067 100
212 213 993595 100
213 214 968063 100
213 214 85796 46
214 215 910528 100
215 216 888672 100
215 216 142288 70
216 217 926173 100
216 217 132276 75
216 217 287684 76
216 217 54824 57
217 218 974644 100
218 219 978187 100
218 219 812761 98
218 219 115431 23
219 220 978863 100
220 221 986581 100
220 221 62834 96
220 221 489988 70
221 222 980276 100
222 223 935757 100
222 223 515928 89
222 223 67164 75
222 223 59929 59
223 224 882401 100
224 225 990004 100
225 226 974341 100
225 226 80228 10
226 227 879160 100
227 228 960326 100
228 229 983025 100
228 229 176589 49
228 229 217159 81
229 230 982957 100
229 230 588927 100
230 231 985863 100
230 231 45642 9
231 232 980281 100
231 232 158041 60
231 232 539364 97
232 233 836045 100
232 233 5880 24
232 233 409790 70
233 234 999182 100
234 235 986103 100
235 236 973259 100
236 237 946251 100
237 238 995628 100
238 239 981507 100
239 240 962653 100
239 240 234868 98
239 240 3027 61
240 241 959115 100
240 241 9212 43
241 242 917618 100
241 242 35544 57
241 242 5694 37
242 243 985449 100
243 244 920497 100
244 245 947502 100
245 246 988902 100
245 246 134252 2
246 247 976154 100
246 247 176663 97
247 248 999150 100
248 249 989917 100
248 249 59104 37
249 250 923660 100
249 250 284076 93
249 250 293075 98
249 250 3614 76
249 250 36098 25
249 250 216696 35
250 251 983483 100
250 251 64510 31
251 252 985665 100
251 252 90323 10
252 253 952161 100
252 253 98802 75
253 254 919354 100
253 254 138130 49
254 255 973735 100
254 255 103377 85
255 256 878996 100
255 256 139056 39
256 257 979999 100
256 257 27951 16
257 258 985533 100
257 258 21390 46
257 258 26090 19
257 258 295807 58
258 259 981374 100
258 259 6538 5
259 260 980971 100
260 261 949780 100
260 261 111786 38
261 262 995665 100
262 263 915913 100
263 264 952117 100
264 265 988706 100
265 266 795322 100
265 266 36241 62
266 267 955538 100
266 267 33485 46
267 268 997415 100
267 268 64983 24
268 269 929197 100
268 269 713175 99
269 270 999529 100
269 270 203796 90
270 271 981263 100
271 272 992296 100
272 273 975668 100
272 273 84632 61
272 273 150299 14
273 274 978472 100
273 274 7292 75
274 275 992198 100
275 276 879400 100
276 277 997901 100
276 277 181914 24
276 277 104919 73
277 278 958366 100
278 279 996879 100
278 279 164454 100
279 280 920416 100
279 280 163815 100
279 280 270015 68
279 280 173622 72
280 281 994182 100
280 281 175948 37
280 281 15746 72
281 282 931317 100
281 282 151859 55
282 283 979242 100
283 284 966457 100
283 284 169234 30
284 285 957648 100
284 285 83025 88
285 286 980204 100
286 287 936129 100
287 288 996496 100
287 288 171786 100
287 288 106279 21
287 288 72062 45
288 289 959323 100
288 289 72219 37
289 290 859085 100
289 290 127733 32
290 291 948186 100
291 292 991538 100
291 292 331514 79
292 293 941521 100
293 294 925474 100
293 294 52462 41
293 294 57405 99
294 295 928880 100
294 295 96354 5
294 295 25229 19
294 295 107434 83
294 295 45640 41
294 295 546171 82
295 296 869284 100
296 297 969324 100
296 297 205099 54
296 297 223546 31
296 297 143493 39
297 298 892892 100
297 298 135372 74
297 298 92010 97
298 299 819446 100
298 299 223693 73
298 299 226742 100
299 300 992562 100
299 300 125882 75
299 300 31487 20
300 301 978866 100
300 301 11178 3
301 302 935914 100
302 303 985909 100
303 304 942061 100
304 305 964631 100
304 305 90559 44
305 306 958007 100
305 306 174606 16
305 306 99883 46
305 306 28121 22
306 307 992709 100
306 307 64820 84
306 307 7718 53
307 308 865797 100
308 309 991063 100
308 309 146923 24
309 310 972861 100
309 310 470305 42
309 310 65527 36
310 311 999235 100
310 311 80544 57
311 312 969229 100
312 313 932586 100
312 313 324860 57
313 314 959538 100
314 315 918961 100
314 315 17785 4
314 315 241947 60
315 316 980203 100
316 317 952064 100
317 318 931537 100
318 319 944651 100
319 320 999981 100
319 320 334327 86
319 320 150465 5
320 321 817374 100
320 321 19322 34
321 322 998584 100
322 323 979082 100
323 324 987122 100
324 325 921794 100
324 325 311718 85
325 326 950124 100
325 326 27384 30
326 327 996289 100
326 327 162587 77
327 328 957447 100
327 328 119277 15
328 329 998054 100
328 329 382512 96
329 330 985004 100
330 331 975309 100
330 331 241695 66
331 332 947857 100
331 332 60759 71
331 332 257970 80
332 333 946583 100
332 333 74383 4
332 333 33665 58
333 334 945624 100
333 334 38916 57
334 335 992443 100
334 335 216991 89
335 336 919954 100
335 336 224679 8
336 337 999194 100
337 338 982428 100
337 338 125440 54
338 339 978414 100
338 339 134791 57
338 339 434974 78
339 340 940987 100
339 340 52554 29
340 341 940810 100
341 342 995043 100
342 343 970065 100
342 343 692838 97
342 343 259612 84
343 344 992338 100
343 344 184328 85
344 345 962099 100
345 346 998919 100
345 346 165675 25
346 347 932572 100
347 348 963980 100
347 348 220331 52
348 349 939007 100
348 349 115932 1
349 350 982555 100
349 350 69330 42
349 350 6464 83
350 351 980349 100
351 352 647229 100
352 353 890636 100
352 353 354942 90
353 354 975751 100
353 354 186910 3
353 354 72882 27
354 355 859973 100
354 355 390630 56
354 355 282918 62
354 355 225300 76
355 356 957530 100
355 356 63067 43
355 356 3174 32
356 357 988617 100
356 357 36476 7
356 357 377156 73
357 358 905166 100
357 358 258016 62
358 359 934961 100
358 359 86045 66
358 359 86343 5
358 359 18864 46
359 360 939351 100
359 360 234684 14
360 361 877380 100
360 361 80917 17
360 361 143970 43
360 361 160253 61
361 362 995271 100
362 363 929503 100
362 363 97496 43
362 363 26162 99
363 364 999938 100
363 364 135337 89
363 364 454802 57
364 365 990956 100
365 366 961931 100
366 367 990488 100
366 367 398377 73
367 368 958248 100
368 369 955568 100
368 369 247000 82
368 369 270679 87
369 370 959429 100
369 370 106861 55
369 370 106932 56
370 371 996505 100
371 372 924044 100
371 372 101205 97
372 373 968144 100
373 374 991920 100
373 374 274420 87
373 374 325400 82
374 375 988844 100
375 376 998965 100
376 377 938104 100
376 377 23830 27
377 378 978881 100
378 379 959780 100
378 379 217763 27
378 379 42972 77
379 380 999783 100
380 381 910780 100
380 381 312047 78
381 382 926370 100
381 382 385259 89
382 383 920240 100
382 383 6485 3
383 384 974893 100
384 385 998295 100
384 385 131515 15
384 385 32045 18
385 386 975264 100
385 386 345951 72
385 386 157732 31
386 387 964858 100
387 388 987288 100
387 388 16822 30
387 388 242565 96
388 389 922459 100
389 390 991287 100
389 390 63650 8
390 391 925160 100
390 391 31320 17
391 392 908761 100
391 392 105857 27
391 392 332444 93
392 393 955248 100
392 393 80389 16
393 394 971271 100
393 394 96522 44
394 395 998267 100
394 395 137903 33
394 395 178003 60
394 395 141589 44
395 396 977278 100
395 396 118318 34
396 397 989847 100
396 397 80502 64
397 398 945405 100
397 398 15340 23
398 399 970184 100
398 399 26611 29
398 399 58680 20
398 399 337364 85
399 400 913962 100
400 401 981976 100
400 401 5129 25
401 402 851545 100
401 402 794622 98
402 403 991571 100
403 404 927895 100
403 404 25956 64
403 404 50373 9
404 405 994847 100
405 406 994545 100
405 406 209676 30
406 407 932670 100
406 407 4167 78
407 408 965488 100
407 408 29290 3
408 409 920071 100
408 409 212020 68
409 410 984315 100
410 411 987900 100
410 411 115831 82
411 412 870590 100
411 412 83155 23
411 412 75043 32
412 413 954524 100
412 413 620858 95
412 413 148239 8
413 414 965931 100
414 415 994062 100
414 415 24921 1
415 416 883767 100
415 416 175500 46
416 417 999165 100
416 417 405733 67
417 418 965503 100
418 419 998958 100
418 419 124351 61
419 420 997299 100
419 420 57161 40
420 421 946199 100
420 421 460962 66
420 421 47682 14
420 421 104780 62
421 422 984306 100
421 422 27555 48
422 423 895027 100
423 424 977530 100
424 425 998090 100
425 426 999331 100
426 427 983471 100
426 427 462756 93
427 428 991831 100
427 428 15163 49
428 429 926201 100
428 429 34629 7
428 429 115562 66
428 429 112255 50
429 430 944483 100
429 430 72590 2
429 430 17589 13
430 431 999123 100
430 431 260710 79
431 432 992825 100
431 432 435878 98
432 433 999064 100
433 434 966246 100
433 434 3143 1
434 435 991801 100
435 436 960122 100
436 437 979380 100
436 437 42570 86
437 438 939539 100
437 438 11466 56
437 438 155853 78
438 439 991262 100
439 440 926098 100
439 440 404088 62
439 440 65351 94
440 441 921070 100
440 441 31722 33
440 441 90255 6
441 442 994259 100
441 442 81304 52
441 442 114147 3
442 443 905182 100
442 443 91597 85
443 444 963219 100
444 445 997753 100
444 445 51985 15
445 446 984300 100
445 446 89811 50
445 446 301564 71
446 447 995123 100
446 447 426838 42
447 448 830343 100
448 449 931101 100
448 449 5221 14
448 449 18169 74
448 449 495652 73
448 449 95189 13
448 449 12424 12
449 450 964435 100
449 450 280551 19
450 451 984319 100
450 451 16267 90
450 451 402931 57
450 451 997 25
451 452 955173 100
451 452 60146 34
452 453 964472 100
453 454 957933 100
454 455 977729 100
454 455 68502 12
455 456 941619 100
455 456 231337 25
456 457 968539 100
457 458 960513 100
457 458 12161 68
458 459 984881 100
458 459 75444 33
458 459 238670 29
459 460 955863 100
459 460 434886 64
460 461 958548 100
460 461 80311 29
460 461 356 67
461 462 914772 100
461 462 37506 85
462 463 975743 100
462 463 413303 80
463 464 923328 100
463 464 95583 15
464 465 970058 100
465 466 986467 100
465 466 370824 2
465 466 274540 90
466 467 983313 100
466 467 33314 81
467 468 872575 100
467 468 639864 95
468 469 967108 100
468 469 125942 39
468 469 129528 47
469 470 966923 100
470 471 994737 100
470 471 676975 82
471 472 999247 100
472 473 950027 100
473 474 827877 100
474 475 907836 100
474 475 342557 76
475 476 940602 100
475 476 156164 54
475 476 200478 50
476 477 992060 100
476 477 27313 51
476 477 18473 35
477 478 928601 100
477 478 110638 48
478 479 999107 100
478 479 96211 84
479 480 913603 100
479 480 15803 29
479 480 306015 94
480 481 988701 100
480 481 64681 90
481 482 979801 100
481 482 189199 84
482 483 966441 100
482 483 26856 74
483 484 972384 100
483 484 163436 46
484 485 998899 100
485 486 996303 100
485 486 145118 50
486 487 918212 100
486 487 37604 10
487 488 991501 100
488 489 968882 100
488 489 152177 31
488 489 233864 8
489 490 905694 100
489 490 564167 92
489 490 1085 32
489 490 43272 15
490 491 957167 100
491 492 995538 100
492 493 923521 100
492 493 4093 39
493 494 986057 100
493 494 7573 4
494 495 975269 100
494 495 111054 43
494 495 37950 58
494 495 77244 87
495 496 980128 100
495 496 191660 77
495 496 96701 37
496 497 933403 100
496 497 48200 53
496 497 83962 22
497 498 850530 100
497 498 598395 91
497 498 47452 42
498 499 995589 100
498 499 62264 59
499 500 436849 100
