4
500 1000 1000
9010000000 9820000000
1 2 827380 100
2 3 938947 100
2 3 91740 19
2 3 1276 3
2 3 51502 20
2 3 207981 5
3 4 965372 100
3 4 189528 92
4 5 967592 100
4 5 337601 47
4 5 61357 28
5 6 991276 100
5 6 101757 14
5 6 63564 26
6 7 956589 100
6 7 716373 94
7 8 913044 100
7 8 55591 18
8 9 980085 100
8 9 130959 45
9 10 953881 100
9 10 209487 2
10 11 845125 100
11 12 994594 100
11 12 359190 73
11 12 129245 74
12 13 989381 100
12 13 64798 9
12 13 719241 97
12 13 181288 10
13 14 887796 100
14 15 942219 100
14 15 81892 39
15 16 944525 100
15 16 43017 97
15 16 80542 42
16 17 980018 100
16 17 123808 36
16 17 199918 29
16 17 9260 62
17 18 983348 100
17 18 126401 25
18 19 965675 100
19 20 814170 100
19 20 320249 24
20 21 992689 100
20 21 702940 81
21 22 978553 100
22 23 848166 100
22 23 365093 45
22 23 512014 85
23 24 973173 100
24 25 974201 100
24 25 117941 55
25 26 990573 100
26 27 898681 100
26 27 440957 68
27 28 965507 100
28 29 986008 100
29 30 985365 100
29 30 195478 55
29 30 55070 76
30 31 988974 100
30 31 556564 51
30 31 161900 9
31 32 966667 100
31 32 215499 20
31 32 298659 66
32 33 994144 100
32 33 173660 35
32 33 153859 40
33 34 914680 100
33 34 119668 65
33 34 140902 74
33 34 191547 85
34 500 724902 100
1 35 28237 100
35 36 971828 100
35 36 118522 43
36 37 971470 100
37 38 948204 100
38 39 981130 100
38 39 47507 79
39 40 878934 100
40 41 927816 100
41 42 911234 100
41 42 106768 63
42 43 981677 100
43 44 945048 100
43 44 159087 58
44 45 979513 100
45 46 941852 100
46 47 983132 100
46 47 48460 46
46 47 94964 69
47 48 959519 100
47 48 18587 40
48 49 957046 100
49 50 879278 100
49 50 60485 69
49 50 109151 52
49 50 297575 81
50 51 989016 100
51 52 928197 100
51 52 147265 37
52 53 844466 100
52 53 53517 20
53 54 910884 100
53 54 32856 13
54 55 908026 100
55 56 967542 100
55 56 205028 57
55 56 314968 80
56 57 950154 100
56 57 127730 52
57 58 994501 100
57 58 208354 11
57 58 672050 86
58 59 971620 100
59 60 954028 100
59 60 155534 91
59 60 201075 58
60 500 871548 100
1 61 672217 100
61 62 963189 100
61 62 46178 11
62 63 906318 100
62 63 4578 51
63 64 854810 100
63 64 170426 47
64 65 986862 100
65 66 958368 100
65 66 11190 1
65 66 520755 94
66 67 999698 100
67 68 975816 100
68 69 994515 100
68 69 18053 80
69 70 999574 100
70 71 905222 100
71 72 987673 100
72 73 996643 100
72 73 53577 61
72 73 231706 47
72 73 147470 59
73 74 974157 100
73 74 24806 50
74 75 985008 100
74 75 191068 78
75 76 937282 100
75 76 277480 61
76 77 980278 100
76 77 20337 51
77 78 964291 100
78 79 956527 100
79 80 744188 100
79 80 121015 80
79 80 81685 68
80 81 983656 100
81 82 994217 100
81 82 40399 31
82 83 969221 100
82 83 129149 100
83 500 557586 100
1 84 188009 100
84 85 819117 100
84 85 98423 36
84 85 216950 79
84 85 32162 48
85 86 947190 100
86 87 912113 100
87 88 990770 100
88 89 986275 100
88 89 345780 97
88 89 241094 99
88 89 83353 9
89 90 946242 100
90 91 928407 100
91 92 947671 100
91 92 115757 40
92 93 970747 100
92 93 40682 24
92 93 74574 9
93 94 951154 100
94 95 955860 100
95 96 987454 100
95 96 140272 65
95 96 122440 58
96 97 985612 100
97 98 972320 100
97 98 79900 41
98 99 985491 100
98 99 243482 44
98 99 36572 26
99 100 985975 100
100 101 949913 100
100 101 309528 3
101 102 952862 100
101 102 13208 53
102 103 978893 100
103 104 963350 100
103 104 92314 64
103 104 2545 73
104 105 988848 100
104 105 240929 65
105 106 999948 100
105 106 205814 60
105 106 156820 12
106 107 981284 100
106 107 312382 86
107 108 920475 100
107 108 33742 92
108 109 924062 100
109 500 650721 100
1 110 254376 100
110 111 942410 100
111 112 989064 100
111 112 153735 15
111 112 10381 4
111 112 12156 60
112 113 998450 100
112 113 78163 58
113 114 970543 100
113 114 193224 52
114 115 978220 100
114 115 75496 50
114 115 94782 17
115 116 899205 100
116 117 875101 100
117 118 998510 100
117 118 52207 79
118 119 996713 100
118 119 2736 20
118 119 366394 93
118 119 73263 10
119 120 973479 100
120 121 875460 100
120 121 44777 87
121 122 991134 100
121 122 270327 54
121 122 14448 64
121 122 43485 48
122 123 935036 100
122 123 48657 6
122 123 57524 87
122 123 53523 19
123 124 969195 100
123 124 51073 72
124 125 993696 100
125 126 949717 100
125 126 244537 60
126 127 953627 100
126 127 342433 41
127 128 980961 100
127 128 278899 85
127 128 14956 39
128 129 930729 100
128 129 5804 35
128 129 187060 68
129 130 854352 100
129 130 148402 12
130 131 847660 100
130 131 114567 61
130 131 33923 26
130 131 260473 98
131 132 949176 100
131 132 6433 28
131 132 273986 95
131 132 25474 23
131 132 340792 80
132 133 963099 100
133 134 990199 100
133 134 59277 25
133 134 87487 39
133 134 124556 47
134 135 944696 100
134 135 656 40
135 500 716458 100
1 136 182419 100
136 137 967531 100
136 137 652596 92
137 138 952100 100
137 138 26102 39
137 138 21635 53
138 139 978303 100
138 139 54803 58
139 140 958659 100
140 141 999313 100
140 141 101271 95
141 142 911127 100
141 142 38118 17
142 143 938622 100
143 144 997656 100
143 144 124716 23
143 144 393714 62
144 145 934499 100
145 146 991436 100
145 146 7010 67
146 147 988190 100
147 148 984941 100
148 149 942577 100
148 149 10614 40
149 150 953123 100
149 150 232929 94
150 151 909014 100
150 151 403088 93
150 151 111438 32
151 152 995210 100
151 152 727548 94
152 153 970745 100
153 154 957983 100
153 154 181576 78
154 155 943230 100
154 155 138621 99
155 156 936195 100
156 157 914396 100
157 158 985785 100
157 158 44842 23
157 158 571130 92
158 159 971768 100
158 159 728020 100
159 160 962602 100
160 500 849428 100
1 161 212129 100
161 162 907992 100
162 163 968717 100
163 164 913569 100
164 165 876251 100
165 166 945749 100
166 167 960883 100
167 168 994936 100
168 169 926814 100
168 169 118715 36
168 169 361408 94
169 170 978278 100
169 170 356188 90
169 170 103781 34
170 171 980355 100
170 171 14760 95
170 171 62686 28
171 172 944657 100
171 172 47837 53
171 172 243854 77
171 172 218559 86
172 173 908961 100
173 174 986985 100
173 174 18182 49
173 174 297095 61
174 175 983107 100
175 176 957193 100
176 177 998658 100
177 178 994433 100
178 179 909356 100
179 180 974062 100
179 180 104312 47
180 181 889456 100
180 181 15853 56
180 181 173150 37
181 182 943492 100
181 182 97472 75
181 182 6762 3
181 182 17641 48
181 182 34710 53
182 500 213799 100
1 183 10900 100
183 184 994410 100
184 185 974952 100
184 185 421343 88
185 186 916266 100
185 186 153322 23
186 187 873333 100
186 187 110560 56
187 188 873183 100
187 188 104326 26
187 188 123202 24
187 188 69016 78
187 188 38756 79
188 189 963344 100
188 189 183700 43
188 189 16987 42
189 190 960983 100
189 190 48207 8
189 190 116157 27
189 190 4110 23
190 191 944258 100
191 192 877346 100
192 193 986012 100
193 194 958589 100
193 194 383577 98
194 195 947670 100
195 196 959482 100
196 197 953967 100
197 198 989274 100
197 198 166257 45
197 198 108519 11
198 199 976800 100
199 200 905877 100
199 200 70566 62
200 201 982834 100
200 201 385205 76
200 201 65619 62
200 201 655104 94
200 201 341419 100
201 202 992054 100
201 202 111502 89
201 202 361522 99
202 203 898158 100
202 203 103622 31
203 204 949155 100
204 205 974238 100
204 205 16554 4
205 206 931869 100
205 206 38103 28
205 206 118088 90
206 207 981552 100
206 207 57936 40
206 207 138299 17
206 207 66721 57
207 500 3968 100
1 208 555557 100
208 209 960585 100
208 209 108497 69
208 209 23898 10
209 210 974425 100
210 211 967542 100
210 211 89349 52
210 211 329337 55
211 212 989037 100
211 212 113905 47
212 213 963469 100
213 214 899228 100
214 215 925655 100
214 215 49652 3
214 215 214768 23
215 216 942656 100
215 216 27166 15
215 216 15515 82
216 217 971591 100
216 217 7213 19
217 218 998372 100
218 219 997135 100
218 219 95733 73
218 219 164883 45
219 220 939575 100
219 220 83585 11
219 220 120403 18
219 220 66197 66
220 221 899534 100
221 222 958720 100
222 223 860139 100
223 224 973584 100
223 224 47947 9
223 224 807969 94
224 225 910265 100
224 225 269765 57
224 225 181592 6
224 225 158195 31
224 225 150828 88
225 226 914681 100
225 226 656462 58
226 227 982917 100
226 227 216899 57
227 228 890136 100
228 229 963140 100
228 229 90238 30
229 230 991812 100
230 231 953958 100
231 500 663015 100
1 232 944110 100
232 233 881520 100
233 234 941201 100
234 235 992351 100
234 235 137753 30
234 235 39495 27
234 235 110778 5
235 236 994227 100
235 236 165130 37
236 237 951812 100
236 237 144783 70
237 238 946317 100
237 238 102731 33
237 238 294657 88
238 239 976451 100
238 239 153437 78
239 240 997317 100
239 240 15821 70
240 241 960875 100
240 241 418464 100
241 242 955718 100
241 242 168266 70
241 242 64123 45
242 243 978142 100
242 243 351041 75
243 244 917870 100
243 244 81216 59
244 245 965946 100
244 245 182214 81
244 245 91909 58
244 245 153847 56
245 246 916774 100
246 247 932005 100
246 247 608450 100
246 247 120615 67
246 247 369694 85
247 248 966408 100
248 249 994926 100
249 250 957430 100
249 250 161012 84
250 251 976994 100
250 251 335913 100
251 252 998258 100
252 253 984702 100
252 253 24214 100
253 254 981425 100
253 254 167898 90
253 254 156125 23
253 254 159819 69
254 255 960450 100
255 256 998779 100
255 256 30834 29
255 256 66587 57
255 256 92785 87
256 500 220348 100
1 257 369585 100
257 258 979026 100
258 259 937546 100
258 259 85723 74
258 259 159825 94
258 259 53802 30
259 260 994820 100
259 260 34662 31
260 261 993499 100
260 261 132432 36
260 261 190516 19
261 262 944254 100
262 263 992317 100
263 264 995785 100
264 265 948815 100
265 266 924218 100
266 267 928941 100
267 500 528484 100
1 268 795700 100
268 269 983113 100
268 269 273554 80
269 270 998283 100
269 270 19603 25
269 270 82295 55
269 270 80894 97
270 271 957912 100
270 271 92545 21
271 272 947095 100
272 273 914903 100
272 273 329678 64
272 273 21923 27
272 273 49578 50
272 273 456530 72
272 273 154022 22
273 274 867339 100
273 274 29387 96
273 274 261785 38
274 275 941007 100
275 276 862400 100
275 276 85430 18
275 276 48050 23
275 276 46182 37
276 277 947941 100
277 278 972293 100
277 278 6047 54
277 278 39235 96
278 279 962058 100
279 280 969303 100
279 280 133023 43
280 281 981287 100
281 282 931343 100
281 282 8458 49
281 282 133337 61
282 283 993133 100
283 284 953148 100
283 284 118534 52
284 285 931053 100
284 285 2683 1
284 285 92797 4
284 285 45707 79
285 286 999030 100
285 286 196462 81
285 286 676731 60
286 287 971954 100
286 287 246751 66
287 288 982941 100
287 288 585369 91
288 289 851083 100
288 289 90627 54
288 289 172937 39
289 290 973543 100
289 290 9249 30
289 290 33542 39
290 291 951907 100
291 292 984376 100
291 292 288272 53
291 292 437831 94
292 500 812023 100
1 293 983869 100
293 294 916759 100
294 295 996809 100
295 296 989436 100
296 297 852996 100
296 297 3478 85
297 298 936898 100
297 298 92498 41
298 299 991199 100
298 299 214454 31
298 299 55856 72
299 300 973703 100
299 300 60017 80
300 301 916722 100
300 301 45454 35
300 301 2514 97
300 301 23813 90
301 302 973925 100
301 302 169143 21
301 302 160700 66
302 303 995667 100
302 303 419472 95
303 304 933777 100
303 304 60542 39
304 305 982831 100
304 305 78330 16
305 306 888648 100
305 306 84768 74
305 306 41642 82
305 306 7388 7
306 307 922346 100
307 308 997661 100
307 308 194757 61
307 308 176493 46
308 309 950519 100
308 309 287895 59
308 309 529232 72
309 310 888350 100
310 311 997783 100
310 311 239927 66
311 312 982187 100
312 313 993615 100
313 314 972808 100
313 314 63309 1
314 315 780299 100
315 316 855644 100
316 317 954385 100
316 317 27476 18
317 318 952370 100
317 318 1485 38
318 500 215460 100
1 319 820651 100
319 320 986430 100
319 320 55325 20
319 320 75073 100
320 321 974330 100
320 321 756073 95
321 322 984239 100
322 323 973670 100
323 324 936666 100
323 324 21227 47
324 325 958197 100
324 325 116796 28
324 325 51125 73
325 326 996736 100
325 326 426069 81
326 327 930880 100
326 327 242051 39
327 328 937899 100
327 328 603022 76
328 329 982304 100
328 329 232896 97
328 329 130134 100
329 330 996395 100
330 331 918798 100
330 331 148968 79
330 331 175848 14
331 332 976674 100
332 333 980455 100
332 333 43835 27
333 334 960314 100
333 334 281515 97
334 335 972605 100
334 335 259239 63
334 335 65590 48
334 335 5787 67
335 336 945919 100
336 337 859660 100
336 337 821171 100
337 338 995180 100
337 338 43166 11
338 339 972779 100
339 340 951423 100
339 340 16645 28
339 340 126349 89
340 341 920426 100
340 341 95075 44
340 341 117660 90
341 342 972504 100
341 342 404209 73
342 343 997909 100
343 344 962754 100
343 344 278838 95
343 344 184048 39
344 345 984606 100
344 345 182865 37
345 346 990775 100
345 346 535680 84
346 347 976473 100
347 348 990674 100
347 348 132828 84
347 348 58009 52
348 500 696453 100
1 349 26777 100
349 350 994055 100
350 351 954317 100
350 351 131044 21
350 351 663868 95
351 352 846880 100
352 353 934634 100
353 354 965232 100
354 355 943933 100
354 355 27505 51
355 356 989088 100
356 357 983774 100
356 357 320785 85
357 358 988853 100
357 358 180094 73
358 359 916956 100
358 359 509 46
358 359 196488 20
359 360 954649 100
359 360 161105 21
360 361 981452 100
360 361 16748 12
361 362 945163 100
362 363 880892 100
363 364 994882 100
363 364 439448 93
364 365 975935 100
364 365 98327 95
365 366 950448 100
365 366 109787 7
366 367 929041 100
366 367 72922 46
367 368 942022 100
368 369 992792 100
369 370 984970 100
369 370 9161 71
369 370 189198 64
370 371 901211 100
371 372 967082 100
372 373 985825 100
372 373 407563 83
373 500 429864 100
1 374 603286 100
374 375 961582 100
374 375 183696 63
374 375 182657 9
375 376 952807 100
376 377 963216 100
376 377 6634 35
376 377 103483 2
377 378 926161 100
377 378 255195 29
378 379 944882 100
378 379 23139 52
378 379 104873 97
379 380 997696 100
380 381 998827 100
380 381 278432 69
380 381 141973 37
381 382 999803 100
381 382 155865 63
381 382 117490 37
382 383 966195 100
382 383 153182 17
383 384 983718 100
383 384 93264 87
384 385 931933 100
385 386 960546 100
386 387 963630 100
386 387 260436 97
386 387 15695 16
387 388 909453 100
388 389 983063 100
389 390 947285 100
390 391 983811 100
390 391 500688 76
391 392 982095 100
391 392 245227 13
392 393 896391 100
392 393 35365 7
393 394 999052 100
394 395 914877 100
395 396 885831 100
395 396 86409 4
396 397 989283 100
396 397 165999 78
397 398 972372 100
397 398 957906 98
398 399 966127 100
398 399 176639 3
399 400 987941 100
399 400 111781 39
400 401 996584 100
400 401 5118 46
400 401 222862 5
400 401 18360 73
401 402 965420 100
402 403 986168 100
403 404 973720 100
403 404 99349 75
404 405 920101 100
405 500 834182 100
1 406 153149 100
406 407 997935 100
406 407 27463 35
407 408 957473 100
407 408 587280 92
408 409 989549 100
409 410 976682 100
410 411 968022 100
410 411 110444 7
410 411 140514 29
411 412 992966 100
411 412 61303 18
411 412 753455 77
412 413 945731 100
412 413 80023 15
413 414 965089 100
414 415 982598 100
414 415 141010 14
415 416 940018 100
415 416 23283 26
416 417 939096 100
416 417 138119 46
417 418 956983 100
417 418 880496 92
417 418 59450 16
418 419 932400 100
418 419 398388 78
418 419 494468 78
419 420 975612 100
419 420 169087 68
420 421 996697 100
420 421 52358 58
421 422 964833 100
422 423 986966 100
422 423 130954 49
423 424 948199 100
424 425 987321 100
424 425 50667 34
424 425 71833 31
424 425 27112 11
425 500 266418 100
1 426 884740 100
426 427 942795 100
426 427 473199 82
427 428 973368 100
428 429 977497 100
429 430 951004 100
429 430 301448 78
430 431 938152 100
431 432 852305 100
431 432 273119 39
432 433 914331 100
432 433 93778 49
433 434 927301 100
433 434 220691 61
434 435 988364 100
435 436 845767 100
435 436 152522 57
436 437 942213 100
436 437 134383 43
436 437 413784 88
437 438 942491 100
438 439 990821 100
439 440 984439 100
440 441 952054 100
440 441 31270 17
441 442 972402 100
442 443 996071 100
443 444 978969 100
444 445 992665 100
444 445 47561 28
445 446 998901 100
445 446 189981 74
446 447 968537 100
446 447 47045 85
447 448 982527 100
448 449 929725 100
448 449 175269 55
449 450 988434 100
450 451 942665 100
450 451 24 33
451 452 980625 100
451 452 75240 61
452 453 998451 100
452 453 131420 7
452 453 212645 99
452 453 77014 41
452 453 46114 86
453 454 988544 100
453 454 44788 79
454 455 981097 100
454 455 33194 20
455 500 433824 100
1 456 317634 100
456 457 891696 100
456 457 58591 43
456 457 146151 41
456 457 59376 21
457 458 979767 100
458 459 989446 100
458 459 213291 64
458 459 41401 19
459 460 890011 100
460 461 983187 100
461 462 990438 100
462 463 977908 100
463 464 970857 100
463 464 439901 90
463 464 14096 57
464 465 991839 100
464 465 63912 6
465 466 758854 100
466 467 948030 100
467 468 950195 100
467 468 723279 91
468 469 943485 100
469 470 954230 100
469 470 167884 34
470 471 973417 100
470 471 114536 10
471 472 893743 100
472 473 804313 100
472 473 42235 41
472 473 690710 84
472 473 191463 73
473 474 940816 100
474 475 997728 100
474 475 254580 64
475 476 920514 100
475 476 240187 5
476 477 926280 100
476 477 70648 20
476 477 18926 75
476 477 29837 88
477 478 959314 100
478 479 914435 100
478 479 8465 8
479 480 982717 100
479 480 103554 66
480 481 927023 100
480 481 126786 13
480 481 14008 61
481 482 923882 100
481 482 30385 6
482 483 973548 100
482 483 121389 43
482 483 112705 25
483 500 655392 100
1 484 166851 100
484 485 930812 100
484 485 404206 97
484 485 216290 69
485 486 970977 100
485 486 137 15
486 487 869264 100
487 488 981850 100
487 488 456196 36
487 488 162228 87
488 489 948056 100
489 490 948827 100
490 491 922972 100
490 491 59537 60
490 491 59822 32
491 492 844815 100
491 492 644848 62
491 492 90148 40
491 492 310908 17
492 493 947929 100
493 494 901446 100
493 494 125200 67
494 495 915652 100
494 495 334169 80
494 495 176293 49
495 496 744269 100
495 496 114174 89
495 496 55667 36
496 497 819844 100
496 497 37283 42
497 498 970502 100
497 498 447687 89
498 499 970094 100
498 499 112 9
498 499 83149 5
499 500 858440 100
