5
500 1000 1000
59430000000 82040000000
1 2 972577 100
2 6 959452 100
3 4 999201 100
4 5 999210 100
4 15 33812 80
4 10 7155 51
5 12 973628 100
6 8 968179 100
6 8 652138 77
7 8 893599 100
7 14 267207 32
8 9 973393 100
9 11 972938 100
10 13 979633 100
11 13 999610 100
11 16 93907 20
12 14 948379 100
13 16 977445 100
14 15 932239 100
15 16 956110 100
16 18 962923 100
16 21 454119 99
17 19 973974 100
18 20 966254 100
19 20 978462 100
19 23 254050 55
19 20 27741 14
19 23 161603 81
20 24 974691 100
21 23 961782 100
21 42 39216 77
21 23 75013 47
21 29 4778 86
22 24 997989 100
23 24 983885 100
24 25 963648 100
25 29 980416 100
26 31 984554 100
26 43 17282 22
27 30 874380 100
28 30 999204 100
28 29 191747 66
29 33 984014 100
29 35 86095 51
29 36 334197 71
30 34 950638 100
31 32 952740 100
32 33 957436 100
32 46 204486 53
33 35 943411 100
34 35 983422 100
34 40 115485 9
35 37 990783 100
35 36 202863 79
36 38 987270 100
36 39 203945 36
37 42 877379 100
37 47 148211 68
38 43 994409 100
38 50 262763 72
39 40 999570 100
39 51 3457 16
40 42 990882 100
40 49 160168 98
41 45 974354 100
42 45 897245 100
42 52 102534 43
42 47 11164 12
42 50 174736 43
43 49 982206 100
44 45 906467 100
45 46 986928 100
45 46 6391 80
45 56 80519 61
46 48 974196 100
47 50 875717 100
47 49 12778 10
48 51 938986 100
49 54 924718 100
50 51 974628 100
50 69 73438 43
50 52 80839 48
51 52 925954 100
51 58 194495 9
52 54 887430 100
52 54 6450 47
53 57 999851 100
54 56 988758 100
54 66 129590 40
54 55 75829 79
54 78 1151 22
55 58 901061 100
55 72 608847 47
56 57 997779 100
57 60 989000 100
57 71 28092 85
58 60 963078 100
59 62 975980 100
60 65 979653 100
60 70 18187 40
60 82 192418 5
60 68 12077 42
61 65 973982 100
61 66 54367 83
61 62 250762 75
62 64 954567 100
63 64 934933 100
63 71 106399 33
64 70 991562 100
65 68 954976 100
65 68 558670 79
66 68 992712 100
67 68 975656 100
67 76 39744 41
68 69 927812 100
69 71 907847 100
70 77 912004 100
70 74 198267 22
71 74 941245 100
72 73 978018 100
72 74 68911 29
73 74 954159 100
73 75 163708 22
74 82 997390 100
75 76 994522 100
75 81 180182 16
76 78 970532 100
76 83 475110 80
76 80 97175 27
76 77 86113 58
77 78 999761 100
78 80 920183 100
79 83 997853 100
79 87 256278 46
80 81 966873 100
81 84 959710 100
81 87 56367 14
81 85 149227 3
82 87 969875 100
82 83 65781 68
82 84 71520 37
83 84 908041 100
84 88 898374 100
84 87 220677 44
84 85 373420 70
85 88 963154 100
86 89 871364 100
86 117 40183 3
87 88 880494 100
87 94 233569 50
87 96 76693 70
88 90 987836 100
89 95 966891 100
89 94 130531 42
90 92 981924 100
90 96 30982 16
91 93 997654 100
91 99 237358 22
91 96 49301 67
92 94 901865 100
92 97 170258 85
93 100 902053 100
94 98 992899 100
95 102 937145 100
95 113 37648 33
96 104 980082 100
97 99 935022 100
97 104 30328 5
97 100 190407 7
98 101 897718 100
98 103 17068 32
99 107 967315 100
99 100 261434 65
99 103 245245 98
99 101 560702 58
99 101 18601 53
100 101 948198 100
101 102 999074 100
102 106 993887 100
102 106 202938 53
102 107 77579 59
103 104 977102 100
104 105 997343 100
105 107 903117 100
106 107 970560 100
106 115 151805 15
106 120 4852 14
106 108 98447 9
107 109 974771 100
108 110 956917 100
108 123 344135 70
109 112 956949 100
109 118 55871 28
109 119 95885 66
110 111 981344 100
110 112 79182 76
111 115 969198 100
112 113 994046 100
113 114 972393 100
113 114 133546 5
113 140 140212 94
114 118 918751 100
114 117 23358 85
115 117 899824 100
115 120 41102 21
115 135 723851 88
115 123 264248 39
116 118 859849 100
117 118 961178 100
118 119 962555 100
118 120 450486 100
118 126 378119 92
118 131 182849 85
119 120 996010 100
119 135 32302 35
119 129 417917 92
119 133 229862 39
120 123 988888 100
120 128 143775 79
121 122 862183 100
121 123 68409 43
121 134 51447 46
122 123 965082 100
122 126 240575 89
123 124 944878 100
123 145 14385 19
124 125 953339 100
125 126 994202 100
125 127 8768 76
126 127 954818 100
127 129 991475 100
127 139 21478 49
128 131 980308 100
129 130 950109 100
129 138 554817 89
130 133 938335 100
130 131 8951 81
130 138 14674 23
130 133 97274 8
130 137 220048 51
131 132 968461 100
131 136 5541 14
132 141 901393 100
132 135 6176 25
133 137 950994 100
133 136 587568 64
134 136 963142 100
134 146 95415 67
134 135 6378 39
135 136 931061 100
135 140 47517 79
135 144 162280 16
136 143 972691 100
137 139 953044 100
138 144 882950 100
138 139 209082 66
139 142 969196 100
139 141 56350 23
139 153 141616 58
140 143 989365 100
140 147 44444 29
141 144 945232 100
141 157 60849 19
141 142 18075 47
142 143 999897 100
143 145 976832 100
143 156 40973 36
143 148 444207 73
144 145 983541 100
144 155 132359 61
145 157 959438 100
146 148 972441 100
146 173 110994 24
147 148 986805 100
147 150 396955 71
147 167 6374 44
147 175 4232 33
148 153 922056 100
148 154 223086 19
148 152 241559 57
148 169 108178 75
149 154 950715 100
150 151 884625 100
150 159 24026 55
150 154 149576 49
151 152 942394 100
151 160 100311 15
151 152 290562 91
152 153 868428 100
152 163 81481 63
152 157 94848 49
153 154 988010 100
154 158 894296 100
155 157 960336 100
156 157 986001 100
156 158 426477 74
157 160 993183 100
158 160 954656 100
158 159 140697 65
159 161 957106 100
160 172 937639 100
161 165 913924 100
162 168 977104 100
162 166 18592 36
163 165 951175 100
164 168 995952 100
164 169 141757 5
165 167 969315 100
165 174 6731 16
166 167 994046 100
166 170 20227 2
166 169 896308 98
166 167 81037 3
167 168 985471 100
168 173 999564 100
168 174 127096 31
169 178 997315 100
169 173 89701 39
170 172 991020 100
170 173 56288 54
171 173 982045 100
171 174 354221 46
172 175 943790 100
172 178 273114 35
173 175 938592 100
173 174 43887 90
174 175 970894 100
174 185 134287 71
174 179 6839 42
174 180 237775 49
174 180 90072 47
175 177 978830 100
176 177 945095 100
176 200 47954 28
177 181 965479 100
177 182 146182 23
178 179 969777 100
179 182 975667 100
179 180 49117 70
180 182 952730 100
181 182 980413 100
182 183 997011 100
183 184 898891 100
183 195 81843 51
184 185 940579 100
184 195 45843 53
185 186 918313 100
185 190 32913 65
186 196 812509 100
187 190 989584 100
187 202 350147 99
187 190 310828 26
187 189 112216 29
188 189 958715 100
188 195 17064 11
188 199 593123 57
189 190 977983 100
189 191 58728 17
190 192 938351 100
190 200 183881 67
190 191 158912 84
190 194 427849 70
190 212 144411 74
190 192 241316 59
191 198 965604 100
191 198 80336 60
191 194 261793 100
192 194 978865 100
192 193 263202 42
192 197 392391 73
193 197 931700 100
193 196 171006 39
194 196 941779 100
195 199 999225 100
196 197 901280 100
197 198 968545 100
197 200 34739 79
198 208 981604 100
199 201 963303 100
200 208 992215 100
200 217 137599 27
201 209 989507 100
202 203 962863 100
202 219 192971 45
203 206 986539 100
204 211 984542 100
204 214 140618 87
204 208 153400 35
205 206 969209 100
205 212 208934 60
206 207 998884 100
206 208 356192 64
207 211 910134 100
207 217 72445 48
208 209 998811 100
209 210 982852 100
209 216 352137 68
210 212 925949 100
210 218 96892 66
211 213 972008 100
211 212 415107 61
212 213 900351 100
212 223 209103 83
212 218 301245 46
213 214 991740 100
214 216 981900 100
214 215 94650 74
214 224 64520 87
215 216 965852 100
216 217 951675 100
216 218 22286 26
216 226 291497 20
217 220 993900 100
218 223 979193 100
218 223 45795 59
219 221 976572 100
219 228 262834 99
220 224 994720 100
221 222 995593 100
222 224 768607 100
222 225 12990 61
222 258 24113 87
223 227 959770 100
223 234 352653 56
223 225 14037 24
224 227 954857 100
225 227 940971 100
226 229 983004 100
226 231 138812 82
226 240 35209 21
227 231 978795 100
227 237 361148 53
227 235 6918 23
228 230 983654 100
228 232 12662 6
228 246 52 39
229 230 987872 100
230 235 994434 100
231 233 979941 100
231 237 176101 45
231 233 378451 73
232 233 981720 100
232 237 535659 90
233 236 968131 100
234 245 879626 100
234 235 89238 6
235 238 913054 100
235 244 99078 28
235 236 16567 76
235 247 50283 8
236 238 983720 100
236 253 8380 11
237 239 990311 100
238 241 983520 100
238 239 42364 95
239 244 993035 100
240 241 946081 100
241 243 915748 100
242 243 934569 100
242 243 13319 8
243 246 961685 100
244 248 948524 100
245 253 967352 100
245 248 87765 4
246 248 994765 100
246 250 66235 20
247 251 729062 100
247 251 102973 26
247 254 86335 14
248 249 931417 100
248 260 90872 49
248 252 612321 90
249 250 952507 100
249 254 31045 52
250 252 957468 100
250 264 7687 58
251 252 923489 100
251 252 21878 87
252 256 967322 100
252 268 139165 51
252 265 125184 68
253 254 923379 100
253 270 112578 64
254 256 999495 100
254 263 54206 16
254 279 11718 43
255 259 964931 100
256 262 885377 100
256 262 139291 18
257 258 961757 100
258 259 993495 100
258 266 162003 66
258 264 451329 40
258 269 300851 61
259 270 682764 100
260 261 943913 100
260 264 89999 31
260 272 306686 82
260 263 8905 48
261 270 979078 100
261 262 469503 82
262 265 810702 100
262 271 55718 3
262 271 188948 53
263 264 902345 100
264 266 998106 100
264 265 42212 22
265 267 999165 100
266 267 812622 100
266 267 546971 76
266 268 217352 51
266 268 246511 88
267 269 982927 100
267 275 738934 89
268 269 953843 100
268 281 210662 36
268 278 219927 69
268 270 160071 88
268 275 63402 66
269 271 894247 100
270 272 905478 100
270 272 70461 33
271 272 991766 100
271 279 351247 69
272 277 942771 100
272 279 252583 42
273 278 977626 100
273 279 79069 53
274 280 902747 100
274 275 393845 61
275 277 962667 100
275 280 403326 71
275 276 62285 54
276 277 997061 100
276 290 52462 20
276 283 176299 26
277 278 918749 100
277 278 44534 20
277 288 119353 7
278 284 962784 100
279 280 932335 100
280 283 956072 100
280 299 267234 65
280 283 36476 14
281 282 968682 100
281 300 26630 7
281 289 135264 30
282 287 991107 100
282 287 228950 61
283 285 920286 100
284 285 991405 100
284 290 68249 42
285 286 919002 100
286 290 999787 100
286 287 87463 14
287 291 954530 100
287 288 147045 54
288 299 988800 100
288 300 122288 90
289 291 917822 100
289 299 193423 89
289 298 85219 11
290 291 964084 100
290 297 10776 60
290 294 19859 14
291 297 955193 100
291 299 260359 82
291 293 207227 41
291 302 138728 3
292 300 971560 100
292 321 77169 2
293 296 946479 100
293 313 297894 46
293 302 39682 45
294 295 979325 100
295 297 916761 100
296 297 901074 100
296 314 83201 33
297 300 994770 100
298 301 949813 100
299 300 993139 100
300 301 973872 100
301 302 985485 100
301 302 230097 64
302 303 956084 100
302 303 95974 3
302 304 67428 11
302 310 139678 96
303 308 957825 100
304 305 935737 100
305 306 930578 100
305 306 126759 66
305 306 65656 74
306 308 994822 100
306 309 369741 77
306 314 614547 96
307 313 997105 100
307 313 250446 70
307 312 225032 56
308 313 987267 100
308 318 130847 60
308 323 443412 68
309 312 996462 100
310 311 947356 100
310 318 322815 54
311 313 930071 100
311 316 27499 11
312 314 990518 100
313 317 970118 100
314 316 998414 100
315 320 926962 100
316 321 983119 100
316 332 523212 58
317 321 989132 100
317 318 108804 85
317 331 607397 89
318 320 994689 100
319 320 951739 100
319 321 146542 59
319 328 408197 95
320 327 824198 100
320 325 73916 7
321 322 946750 100
321 332 45364 9
321 336 195550 9
321 328 289854 65
322 323 958692 100
322 337 102849 53
323 324 841662 100
323 328 48490 25
324 325 916204 100
325 327 987445 100
325 332 20037 1
325 327 58975 4
325 332 113254 18
326 327 954636 100
326 327 23839 5
327 328 967010 100
327 328 95472 68
327 341 29315 52
328 337 993851 100
328 329 433386 85
328 334 427569 87
328 345 312204 71
328 330 216957 2
328 333 24121 86
329 330 875929 100
329 336 36487 54
330 333 787173 100
330 332 401246 89
330 336 97859 74
331 332 988790 100
331 341 114063 48
331 333 194945 64
332 334 928552 100
333 334 991365 100
334 335 943806 100
335 336 978122 100
336 337 964568 100
336 337 451609 46
337 346 975128 100
338 340 955373 100
338 341 15842 94
338 342 26418 28
339 341 964942 100
339 342 24983 35
340 343 940540 100
340 341 317389 93
341 343 971670 100
341 342 91164 36
342 344 996967 100
343 344 901089 100
343 360 10285 44
344 345 972344 100
345 347 998488 100
345 374 177286 52
345 348 88807 55
346 347 979565 100
346 350 135996 79
346 351 589011 82
346 348 152586 45
347 348 978665 100
348 349 974610 100
349 353 812094 100
350 355 989932 100
350 352 142022 70
351 352 895290 100
351 356 141970 61
351 354 277914 8
352 353 962309 100
352 367 5424 52
352 358 467392 96
353 363 970058 100
353 358 18264 3
353 361 53130 9
354 355 951174 100
354 355 10054 44
355 362 969972 100
355 363 9968 99
356 359 794435 100
356 373 48536 26
356 359 80104 45
356 364 5034 32
356 358 718521 92
357 358 984613 100
357 363 53920 50
358 359 921979 100
359 361 948502 100
359 367 4303 75
359 360 135707 40
360 361 993472 100
360 371 209451 36
361 362 981719 100
361 369 10283 54
362 363 993316 100
363 368 933957 100
364 367 937657 100
364 365 145343 84
364 366 119568 36
365 366 980953 100
366 372 987632 100
366 370 305571 66
367 370 985334 100
367 373 275993 96
367 371 74516 14
368 369 866029 100
368 373 1171 45
368 373 174029 47
369 370 881214 100
370 374 934613 100
371 375 986454 100
371 381 2676 24
371 381 137972 67
371 389 257740 94
372 373 970407 100
373 376 924756 100
373 378 45473 43
373 381 44897 59
374 375 977496 100
374 379 81025 52
374 383 84527 27
374 377 26187 22
374 390 144458 20
375 377 972869 100
375 384 208289 59
375 385 125878 3
376 377 994274 100
376 380 54902 90
377 378 880084 100
377 384 67061 8
378 383 942848 100
378 385 48811 23
378 393 28603 90
378 387 189913 28
379 381 962974 100
380 382 963040 100
381 382 986818 100
381 415 248323 85
381 391 168052 80
382 388 927352 100
382 396 73402 71
382 384 4146 39
383 385 992252 100
384 391 956737 100
384 394 45707 7
385 390 982647 100
385 398 126712 54
386 387 991541 100
387 391 998875 100
387 396 39736 35
388 399 982034 100
389 390 998724 100
389 403 147973 88
389 392 102833 4
390 395 983421 100
390 415 147475 70
390 391 141149 15
391 395 823487 100
391 395 204624 95
392 394 987592 100
392 409 14210 31
392 413 289896 69
393 397 916699 100
393 404 80737 72
394 395 996190 100
395 402 987299 100
396 397 955802 100
397 398 997666 100
398 402 979421 100
398 399 29377 26
398 405 13902 21
399 400 877462 100
400 401 996219 100
400 403 193195 47
400 405 406050 73
401 403 927482 100
402 403 991362 100
402 408 70056 2
402 405 356471 61
403 405 888001 100
403 404 572683 93
403 417 116042 87
404 406 978426 100
404 426 143935 92
405 407 999565 100
405 408 124494 70
405 406 129165 42
405 413 13974 6
406 409 970586 100
406 430 119524 88
406 413 256203 65
407 408 994619 100
408 411 975743 100
409 411 984247 100
410 411 896542 100
411 412 976558 100
412 413 972347 100
413 418 989771 100
414 421 918595 100
414 420 73835 49
414 417 441359 6
415 416 885439 100
416 417 990279 100
417 418 991964 100
417 423 154743 57
418 422 977167 100
418 422 96880 89
418 436 10832 19
418 422 80818 23
419 423 930286 100
419 420 46937 21
420 421 930766 100
420 425 16666 34
420 423 168513 20
421 423 987026 100
421 424 177402 78
422 429 909440 100
422 431 151159 51
423 424 761268 100
423 430 25869 9
424 425 876527 100
425 426 980428 100
425 437 36039 10
425 428 313882 98
426 430 981308 100
426 432 100299 62
427 429 891176 100
427 434 15548 41
427 431 78899 10
427 443 91661 34
428 432 981513 100
428 433 1040 1
429 432 997380 100
429 430 233778 100
430 431 926693 100
430 434 128613 79
431 433 948123 100
431 434 33843 53
431 436 278498 74
432 433 865408 100
432 441 230950 54
433 438 956418 100
433 437 25533 28
434 435 899749 100
434 453 4515 39
435 436 971894 100
435 439 421124 48
435 445 728417 91
436 438 967963 100
436 438 40268 62
436 438 7456 15
437 446 971991 100
437 444 88358 78
438 440 994983 100
438 447 357087 46
438 439 27422 52
439 440 840105 100
440 441 994592 100
441 442 969450 100
441 444 366409 77
442 443 984395 100
443 444 937249 100
443 449 152993 65
443 446 33658 18
444 445 987053 100
444 450 860925 94
445 447 993937 100
446 449 979923 100
446 447 132902 59
447 448 993395 100
447 452 338678 54
448 452 900263 100
449 450 975266 100
449 450 37513 73
449 462 266954 32
450 458 992320 100
450 461 26797 53
450 479 502510 99
451 452 987497 100
451 456 177120 77
452 453 946906 100
452 457 80510 52
453 454 975146 100
454 458 911064 100
455 458 960734 100
456 459 877366 100
457 458 995605 100
457 458 13369 12
458 460 985061 100
458 465 80917 13
458 465 82681 27
459 462 931894 100
460 461 937333 100
460 479 242425 38
460 490 44428 85
461 462 842084 100
461 478 61363 2
461 462 29645 1
462 463 988774 100
463 464 987525 100
463 469 32518 69
464 466 948128 100
464 465 214849 74
465 469 805896 100
466 475 990284 100
466 467 30850 4
467 471 995725 100
467 470 267603 79
468 469 971308 100
469 470 927851 100
469 476 296074 24
470 472 990370 100
470 475 57522 27
470 475 109704 49
471 472 977735 100
471 473 450331 82
472 474 921551 100
472 473 57219 49
472 478 245064 81
473 474 983336 100
473 489 250979 59
473 481 28965 29
473 490 211491 85
474 475 940878 100
475 482 966371 100
475 489 57976 16
475 476 476404 91
475 487 170617 18
476 478 985885 100
477 478 959434 100
477 481 303039 57
478 479 994366 100
478 480 83146 24
478 486 94990 58
478 482 252810 61
479 480 990058 100
480 481 977133 100
480 496 21423 25
481 482 958629 100
482 483 958944 100
482 487 96755 72
483 484 866844 100
483 484 10665 8
483 489 104845 28
483 486 159805 9
484 488 971497 100
485 488 946914 100
485 496 67146 18
485 486 301337 79
486 487 938541 100
486 497 488636 98
487 488 951388 100
488 493 764532 100
488 489 52508 11
489 490 978229 100
490 491 980186 100
491 492 984130 100
491 493 31760 65
491 497 166350 56
492 495 942444 100
492 495 112268 57
492 495 133864 16
493 495 951759 100
493 500 38925 2
493 499 208893 54
493 496 40783 1
493 495 158590 2
494 496 994944 100
494 495 41588 19
494 500 607519 83
495 496 972221 100
496 497 953177 100
496 498 364555 63
497 499 931693 100
497 500 38645 2
497 500 646829 80
498 500 863798 100
499 500 949341 100
499 500 68596 17
499 500 126524 33
