6
500 1000 1000
58140000000 84910000000
1 2 921910 100
1 5 28637 26
1 3 41072 98
2 8 946041 100
2 18 84275 14
3 11 943792 100
4 7 995191 100
4 7 244824 80
4 11 573575 96
5 7 988272 100
6 7 931787 100
6 19 3312 8
6 20 187731 75
7 9 999028 100
7 9 26945 12
8 11 985045 100
8 13 12250 36
9 10 999601 100
9 13 81254 50
10 11 922866 100
10 18 127528 13
10 11 34268 2
11 13 968769 100
11 12 271003 5
12 15 945099 100
13 14 880354 100
14 19 984298 100
15 20 915629 100
16 21 911407 100
16 18 199743 81
16 21 689075 84
17 23 996247 100
17 19 96424 91
18 19 917372 100
19 22 861374 100
20 27 998257 100
21 23 925791 100
22 26 966151 100
22 26 13171 78
22 28 48647 40
22 33 38937 16
23 25 972031 100
23 30 575 6
23 26 169120 72
23 29 34324 59
24 31 994068 100
25 26 976504 100
25 26 217269 57
25 33 57948 56
25 28 547594 92
25 39 489005 98
26 27 902904 100
27 30 918202 100
27 32 53997 2
28 33 908187 100
29 32 936048 100
30 33 981142 100
30 33 229538 49
30 33 470033 100
30 35 645838 83
31 35 998039 100
31 48 124429 60
31 35 8808 13
32 34 914598 100
33 36 952557 100
34 35 966199 100
35 36 995716 100
36 39 954922 100
36 44 13944 31
37 38 959593 100
38 43 957240 100
38 39 240382 70
38 46 17354 89
39 40 988565 100
39 50 53848 48
40 42 981724 100
40 65 56301 50
41 44 992624 100
42 45 870572 100
42 43 16277 21
43 47 950008 100
44 45 942900 100
44 59 120213 88
45 46 860126 100
46 47 936022 100
46 47 94909 28
46 55 18394 58
47 48 985223 100
47 71 111338 91
48 51 815752 100
48 50 23219 78
49 53 990495 100
49 50 48096 37
49 65 240966 88
50 52 941821 100
50 60 359106 41
51 53 970771 100
51 52 57985 88
51 59 131376 21
52 56 929505 100
52 57 106535 46
52 56 764572 98
52 55 101323 32
52 58 186813 57
53 57 964566 100
54 56 964434 100
55 57 927610 100
55 56 69337 68
56 60 997102 100
56 68 247944 68
56 59 52408 47
57 59 859876 100
58 60 970104 100
58 95 419396 71
59 62 964957 100
59 76 64627 53
60 62 882077 100
61 62 980637 100
61 63 202788 82
61 79 33392 34
62 64 963782 100
63 65 986386 100
64 66 933385 100
65 75 957292 100
66 67 978569 100
67 71 868917 100
68 72 912216 100
68 69 124960 11
69 73 986375 100
69 72 729088 92
70 79 855820 100
71 75 988398 100
72 76 938861 100
72 79 166732 92
72 80 162665 79
73 77 942932 100
73 75 26652 17
74 81 939930 100
74 81 68033 68
75 77 963552 100
75 82 57651 45
76 77 992207 100
76 89 117685 90
76 78 49392 23
77 80 983564 100
78 79 998763 100
79 82 877344 100
80 81 988834 100
80 87 115725 2
80 92 105139 35
80 86 81270 83
81 83 980242 100
81 82 85178 81
81 93 74700 45
82 93 955934 100
82 96 1485 16
82 85 439354 95
82 101 198619 75
83 86 955894 100
83 92 44894 46
84 85 966043 100
84 87 758274 95
85 90 939316 100
86 87 990098 100
87 90 844880 100
88 93 893606 100
88 99 69889 11
89 93 973013 100
89 91 59138 44
90 94 964028 100
90 119 219324 72
90 96 162827 63
90 101 64611 88
91 100 959238 100
91 97 35897 15
91 112 146072 43
92 93 996584 100
92 93 302839 39
92 95 303773 85
93 96 996592 100
94 97 973537 100
94 100 124840 62
95 98 995473 100
95 107 114966 99
95 110 313688 86
96 99 955703 100
96 113 4354 70
96 97 275602 2
97 99 957711 100
98 101 962668 100
99 101 954053 100
99 105 708967 37
100 101 995286 100
100 109 65843 33
101 102 836892 100
102 103 827403 100
102 107 162878 31
102 106 256889 47
103 104 968409 100
103 108 137003 32
104 111 996133 100
105 106 951774 100
105 108 44966 84
106 110 911186 100
106 107 259061 89
107 108 948683 100
108 109 982213 100
108 121 52072 23
109 110 965598 100
109 114 113930 31
109 119 72541 1
109 120 136230 89
109 110 282575 69
109 118 237491 60
110 111 944135 100
110 134 350162 81
111 113 804213 100
112 118 923756 100
113 114 969768 100
114 117 973039 100
115 119 984181 100
115 118 6285 20
115 124 184115 45
115 116 83959 69
116 117 962006 100
117 122 995995 100
117 122 259187 37
117 127 92397 36
118 119 930606 100
118 123 272255 96
119 121 996501 100
119 129 3287 40
120 127 930826 100
120 131 208938 60
121 125 918877 100
121 127 77647 78
122 123 970331 100
122 129 338187 78
122 131 310625 2
123 124 986272 100
123 127 176305 45
123 138 486007 92
124 125 972065 100
124 127 1436 56
124 129 32086 12
125 133 986418 100
126 127 964282 100
126 129 27735 77
127 129 992399 100
127 128 116195 54
128 129 992617 100
128 130 150150 30
129 133 962255 100
130 131 979846 100
130 142 343682 75
130 133 71081 58
131 133 973756 100
131 133 480179 98
131 132 663087 100
132 134 958399 100
132 134 276324 76
132 133 59863 67
133 138 985684 100
133 135 182749 56
134 137 977450 100
135 137 981138 100
135 140 250299 71
136 140 969712 100
137 145 962654 100
138 146 992755 100
139 141 968683 100
139 142 206564 46
140 144 859789 100
140 161 64036 11
141 142 971873 100
141 142 79997 71
142 149 973239 100
142 146 32035 23
142 162 275821 92
143 147 974354 100
144 146 950317 100
144 156 251657 61
145 147 933745 100
145 166 567283 99
146 149 996287 100
146 148 34875 52
147 148 995222 100
147 152 138778 38
147 156 166517 32
147 153 54873 34
147 157 4009 19
147 167 58630 12
148 149 977176 100
148 149 117237 94
148 160 79270 19
148 154 156131 19
148 153 294384 67
149 152 975999 100
149 157 110516 9
149 162 186810 62
150 160 938885 100
151 153 975070 100
152 156 982825 100
153 154 993945 100
153 157 51259 70
153 156 32944 73
153 155 25096 19
154 158 955638 100
154 164 109647 76
155 156 924024 100
155 159 82110 63
156 161 956950 100
157 159 973444 100
157 161 306796 90
157 167 475722 74
157 167 122236 9
158 160 914299 100
158 168 535377 95
158 163 406577 77
159 161 967882 100
159 166 274610 31
160 161 936595 100
161 162 989593 100
161 163 13245 68
161 163 182662 12
162 166 974288 100
163 170 988000 100
164 165 896339 100
164 165 60729 8
165 168 867099 100
166 168 957433 100
166 167 40081 23
167 168 994152 100
168 169 966481 100
168 169 145338 45
169 175 996668 100
170 172 999785 100
170 175 272361 13
170 175 200067 67
170 179 44097 57
171 173 948958 100
171 174 13865 10
171 178 42092 25
172 173 932033 100
173 174 985988 100
174 177 959012 100
174 183 18012 70
175 176 894589 100
176 177 985918 100
176 186 814364 82
177 183 977658 100
177 181 102382 40
178 179 992379 100
178 183 18931 51
179 181 885213 100
180 182 949251 100
180 191 93702 88
181 186 963919 100
181 193 102056 62
182 185 991085 100
182 185 102186 21
182 197 444923 9
183 184 981001 100
183 189 181770 26
184 187 988983 100
184 190 54968 54
184 204 51051 66
185 186 966424 100
185 190 25993 87
186 189 935738 100
186 198 16685 62
186 190 623745 96
186 195 7882 27
186 192 400496 96
186 191 132520 70
187 190 907880 100
187 211 73189 49
188 191 990707 100
188 191 354567 84
188 192 76405 6
189 190 980728 100
190 192 997338 100
190 209 21444 31
191 193 924225 100
191 197 30379 96
191 205 26420 55
192 195 953032 100
192 195 1652 72
192 196 87217 38
193 194 988729 100
194 196 997440 100
195 196 916567 100
195 200 227124 9
195 198 29161 84
196 197 996540 100
197 198 974925 100
197 203 451340 72
198 199 890847 100
198 203 251479 82
199 200 891539 100
200 207 816701 100
201 204 958346 100
202 204 999210 100
202 206 36786 19
202 204 329316 60
202 221 96118 89
202 230 12230 4
202 212 159060 5
202 215 7471 8
203 206 968255 100
203 213 269858 80
204 208 951238 100
205 207 925040 100
205 214 33302 70
206 209 978131 100
206 219 32877 25
206 215 2677 63
207 209 935248 100
207 213 381223 46
208 211 847405 100
208 215 319381 60
208 210 9476 81
209 221 942242 100
210 211 924423 100
210 211 70704 35
211 212 934891 100
211 212 4149 40
212 213 994886 100
213 214 976271 100
213 224 202919 88
213 220 13081 11
213 221 259685 62
213 217 60786 5
214 219 975274 100
214 232 305428 71
215 219 951204 100
215 221 36468 73
216 217 900634 100
217 219 976484 100
217 218 98404 46
218 220 956397 100
219 221 959773 100
219 222 96255 34
220 222 947828 100
221 222 964728 100
222 231 930782 100
222 223 380666 93
222 226 21479 84
223 227 927372 100
224 225 991762 100
225 227 937057 100
225 237 125516 47
225 227 363614 95
225 240 378766 75
226 233 865413 100
227 235 996616 100
228 229 959718 100
228 231 246022 12
229 232 983380 100
229 264 49637 11
229 231 166611 80
229 236 98020 90
230 233 984592 100
230 241 16553 78
231 233 924332 100
232 238 965734 100
233 234 964316 100
234 235 965394 100
234 250 60519 19
234 242 63224 30
235 236 999539 100
236 237 910549 100
236 241 406901 93
236 240 31210 87
237 239 953297 100
237 247 20322 29
238 239 995746 100
239 240 977779 100
239 252 427864 88
240 242 796374 100
241 245 983223 100
242 243 965343 100
242 248 304161 21
243 244 992199 100
243 260 491335 96
243 259 431502 65
244 248 929105 100
245 249 969222 100
246 247 910619 100
246 255 105002 7
247 251 932416 100
247 255 37406 80
248 252 984597 100
249 250 882529 100
249 252 112118 76
250 253 959102 100
250 255 88934 84
250 252 42771 15
250 256 333877 45
251 252 960318 100
252 253 918814 100
253 255 999845 100
253 254 498705 57
253 255 173267 58
253 258 96599 50
254 256 941753 100
254 257 200398 79
255 257 967912 100
255 257 67616 60
255 259 334669 31
256 259 931867 100
257 258 962260 100
258 264 990126 100
258 263 103744 37
259 269 994752 100
259 264 14179 60
259 262 374848 80
259 264 7375 53
260 261 900661 100
260 267 213789 9
260 268 114073 58
261 263 852416 100
262 263 999061 100
262 267 124284 25
263 264 860427 100
264 267 866091 100
265 267 990497 100
266 268 975653 100
267 271 943565 100
267 269 78529 27
267 274 77781 3
268 272 995050 100
269 272 908865 100
270 273 960523 100
271 272 870099 100
271 290 29072 61
272 273 907673 100
272 274 75794 66
272 273 60904 28
272 279 133476 94
272 276 127346 63
272 284 221239 40
273 281 921584 100
274 277 956494 100
274 280 140779 59
274 298 50091 40
274 276 402556 83
275 276 991200 100
276 278 992872 100
276 301 32125 29
277 278 990796 100
277 309 101835 26
278 279 984257 100
278 283 10547 12
279 283 991784 100
279 282 238604 89
280 281 980109 100
281 282 917468 100
282 283 998908 100
283 285 877816 100
283 284 15534 13
283 293 155674 34
284 288 977286 100
284 293 149314 64
285 294 964557 100
285 294 391485 60
285 294 41275 39
286 290 947994 100
286 288 96323 34
286 298 26550 63
286 301 11014 58
287 290 962228 100
287 291 211913 27
287 291 1642 16
287 289 3209 23
288 290 943770 100
288 295 145194 90
288 292 350829 58
288 291 179760 53
288 295 345965 89
288 289 457014 42
289 290 972752 100
289 293 535844 91
290 294 966489 100
291 292 953989 100
291 292 29194 45
291 295 253731 43
291 296 231538 88
292 293 717378 100
292 293 244190 93
293 294 947540 100
293 298 25035 53
294 297 941779 100
294 310 52281 37
295 298 996235 100
295 309 430104 66
295 301 393801 67
296 298 950932 100
296 309 199245 50
296 304 420761 51
296 299 558428 98
296 312 11314 84
297 299 976525 100
297 301 118664 27
298 299 966314 100
299 302 931700 100
299 301 22414 15
300 301 919184 100
300 302 33019 78
300 316 34424 88
301 303 993625 100
301 308 5152 98
301 308 268152 65
302 303 924680 100
302 307 112715 8
303 304 993512 100
304 305 981171 100
305 306 953999 100
305 307 9393 41
305 319 114934 4
306 307 930451 100
306 317 211461 46
307 308 915195 100
308 309 968052 100
308 309 120660 4
309 319 936022 100
309 312 7071 39
310 315 927797 100
311 312 900917 100
311 315 128118 29
312 315 807290 100
313 315 946646 100
313 323 235975 38
313 317 86951 72
314 317 959783 100
314 316 191650 27
314 334 97282 96
315 319 957417 100
315 319 44208 27
316 318 922308 100
317 322 973925 100
317 325 216344 96
317 330 581023 62
318 325 989504 100
318 322 272195 62
319 324 997434 100
319 323 3494 60
319 326 141895 45
319 338 17881 30
320 321 819544 100
321 322 971857 100
321 322 279196 60
322 324 960454 100
322 324 200471 24
322 328 364621 32
322 324 103313 81
322 346 127125 27
322 324 76479 50
323 328 982237 100
323 327 106120 83
323 327 280649 74
324 327 971771 100
325 327 966421 100
325 327 273888 58
326 330 996963 100
327 328 990535 100
328 329 982892 100
328 337 59929 54
328 333 84166 52
329 331 933449 100
329 348 4032 58
330 333 904805 100
330 332 40477 83
330 344 232437 15
330 333 100191 72
331 332 923582 100
331 336 238550 16
332 337 992939 100
332 346 1243 25
333 334 910655 100
333 334 67030 61
333 370 284763 86
334 335 943614 100
334 338 79502 51
334 339 18261 82
335 337 969590 100
335 336 18617 41
336 337 978254 100
336 337 285284 25
337 338 902674 100
337 338 66069 40
337 350 104536 6
338 342 968405 100
339 340 995761 100
339 340 13519 6
339 347 213363 53
339 355 128759 78
340 344 999258 100
340 348 13904 53
341 343 976474 100
341 352 84273 87
341 364 62650 10
342 343 999324 100
343 346 965512 100
344 346 999713 100
345 349 997532 100
346 348 962003 100
346 361 225508 33
347 354 931106 100
348 349 961342 100
348 351 332983 82
349 351 910409 100
349 356 38883 81
350 351 863176 100
351 353 972138 100
352 358 964698 100
353 358 989567 100
353 355 142801 23
354 356 951101 100
354 362 331971 17
354 358 96410 72
354 364 87180 37
355 356 858449 100
355 368 391826 100
355 356 40647 10
356 357 994514 100
356 365 35953 69
357 363 923398 100
357 369 34678 5
357 358 126702 18
358 360 980465 100
358 379 541014 87
358 361 210078 90
359 362 968301 100
359 363 32683 27
360 361 963633 100
361 363 841735 100
361 364 43434 15
362 364 891634 100
362 375 56000 19
363 364 983113 100
363 368 627 28
363 371 116699 28
364 369 937693 100
365 367 941970 100
365 366 452413 98
366 367 997519 100
366 386 234451 9
367 368 996740 100
367 374 66508 37
368 371 973737 100
369 372 938921 100
370 373 997525 100
370 372 17474 56
371 374 999837 100
372 376 975827 100
373 374 918183 100
374 376 971705 100
375 376 943189 100
376 377 952155 100
377 378 926813 100
378 383 968641 100
378 381 128867 27
379 384 984415 100
379 391 26230 4
379 392 87609 5
380 381 960375 100
381 382 935461 100
382 383 892629 100
383 386 945926 100
383 388 792679 75
384 385 960797 100
385 386 984871 100
385 391 110909 10
386 388 993425 100
387 390 938893 100
388 391 990927 100
389 390 896458 100
389 398 104566 86
390 394 978974 100
390 393 259611 77
390 405 192666 33
390 403 196742 69
391 392 959138 100
392 394 987631 100
392 394 261952 79
393 394 973295 100
393 417 99990 57
394 396 967868 100
394 397 140992 43
394 397 127857 10
394 395 158974 74
395 396 856560 100
395 397 146511 47
396 397 981877 100
396 398 14755 42
396 413 93933 89
397 399 887284 100
397 399 562672 94
398 399 963457 100
398 411 196287 26
398 415 243315 71
398 401 133374 86
398 411 608557 85
399 406 978930 100
399 407 517415 78
400 404 988216 100
400 408 256386 68
401 408 986157 100
401 423 1427 52
401 413 51803 20
401 403 255610 75
402 404 982468 100
403 404 963304 100
403 405 90274 75
403 408 379086 81
404 408 922789 100
405 408 972988 100
405 414 34838 24
405 407 125931 60
405 411 149053 59
405 409 258217 81
406 407 999884 100
407 411 952037 100
407 408 35891 3
407 412 57117 92
408 409 909073 100
408 412 79545 75
409 414 931983 100
410 413 958727 100
411 416 989174 100
412 414 964541 100
413 414 967702 100
414 419 960771 100
414 421 110514 73
415 416 922471 100
415 425 67118 10
415 422 181851 45
416 419 973165 100
416 428 336141 69
417 419 918087 100
417 418 173933 15
417 422 39122 49
418 422 922175 100
419 420 992462 100
420 422 922531 100
420 423 135233 3
421 423 910686 100
422 427 933325 100
422 428 10093 18
423 425 962768 100
423 429 446865 98
423 433 350313 81
424 426 998931 100
425 429 901357 100
425 426 4272 49
426 430 982436 100
426 430 3707 18
427 428 928102 100
427 457 59726 58
428 435 912800 100
429 430 951956 100
429 435 149396 64
430 435 961030 100
430 452 215134 44
431 433 969379 100
432 433 977618 100
432 439 102871 54
432 441 111497 3
433 436 864470 100
433 442 595587 67
433 441 108892 55
433 438 217731 92
434 440 848992 100
434 446 68895 16
435 437 905291 100
435 448 482951 51
436 439 972296 100
437 439 894629 100
437 446 559214 94
438 439 988765 100
438 443 330694 79
438 446 48047 89
438 439 38188 24
439 441 954785 100
439 441 101999 71
440 442 966992 100
440 442 93156 7
441 444 871535 100
442 445 991178 100
443 445 986874 100
444 447 988196 100
444 445 14959 70
445 446 997339 100
445 456 256320 80
446 450 898067 100
446 459 19719 5
446 460 36641 28
447 453 919925 100
448 449 980532 100
448 452 280215 74
448 460 37711 35
448 453 212659 56
449 450 901658 100
449 469 230846 51
450 452 947128 100
450 469 57099 30
451 457 997357 100
452 454 976339 100
453 459 876991 100
454 457 901246 100
455 460 981229 100
455 456 35304 49
456 457 940407 100
456 476 448417 88
456 464 397273 40
457 458 969347 100
457 491 692420 95
458 463 997642 100
458 460 24764 11
459 462 954184 100
459 482 5792 44
460 461 929998 100
460 463 13635 63
461 475 919583 100
461 463 18962 13
461 469 96524 57
462 465 984472 100
463 464 982025 100
463 465 45501 37
464 466 963918 100
464 468 101525 11
465 467 994748 100
465 480 188634 74
465 466 177545 15
466 467 894086 100
466 482 145849 64
467 470 859531 100
467 482 447856 40
468 469 903011 100
468 472 63525 51
469 470 964184 100
470 471 989090 100
470 488 584 48
470 478 90481 37
471 472 952174 100
471 477 352534 82
472 473 992902 100
472 475 18507 1
473 477 982751 100
473 496 24912 56
473 482 15263 79
473 475 29335 33
474 484 989005 100
475 476 985734 100
475 490 22583 52
475 480 56038 3
476 478 935809 100
476 477 10679 21
477 478 892983 100
477 480 33747 25
478 479 955422 100
478 484 253689 41
479 481 962375 100
480 483 963175 100
481 484 987712 100
481 491 250581 2
482 487 976838 100
483 487 936711 100
483 484 119049 85
484 487 891943 100
484 487 3783 38
485 488 992847 100
485 487 514410 71
485 491 29721 67
486 489 926838 100
487 490 890433 100
487 488 59719 44
487 495 44004 26
488 490 931477 100
489 490 970297 100
489 500 513453 86
489 490 72863 29
490 492 977558 100
491 492 983018 100
491 492 136219 49
492 497 934759 100
492 494 1521 46
492 500 178816 44
493 494 858677 100
494 495 965073 100
494 500 91614 51
494 500 192810 83
495 496 999257 100
496 497 992317 100
497 499 994468 100
497 498 173704 96
498 500 993671 100
498 500 56395 79
499 500 943868 100
