9
500 1000 1000
111660000000 132720000000
1 4 970836 100
1 2 18439 87
1 2 29160 21
2 10 994739 100
2 3 2432 35
2 1 6194 43
3 6 984583 100
4 5 989325 100
5 7 998630 100
5 7 3502 53
5 21 9727 4
5 11 4960 65
6 14 985414 100
7 11 998303 100
8 13 951811 100
8 7 9557 8
9 12 983612 100
10 11 983312 100
10 14 171 3
10 1 1311 35
11 16 995874 100
12 15 983397 100
12 2 3009 81
13 15 990808 100
14 16 998025 100
14 15 2995 63
14 16 12456 67
15 22 986264 100
15 32 2989 70
15 17 28426 24
16 27 960983 100
17 19 997569 100
17 21 3378 11
18 20 993810 100
18 8 1668 66
18 23 24470 78
19 22 993609 100
19 27 10700 97
19 18 7831 35
20 25 979702 100
21 27 997746 100
21 38 17171 90
22 24 998521 100
23 27 998840 100
24 27 992883 100
24 38 39428 55
24 16 2708 97
25 28 988613 100
26 27 994322 100
27 34 993689 100
27 14 27619 29
27 19 1930 59
27 22 11846 46
28 29 983141 100
29 33 988931 100
30 32 977488 100
31 34 995674 100
32 40 999739 100
32 36 6386 77
33 36 998009 100
33 25 8392 1
34 45 989887 100
35 36 989025 100
35 36 5238 92
36 42 975543 100
37 46 989639 100
38 47 994619 100
38 33 3367 96
39 40 998526 100
39 46 6943 15
39 41 1956 38
40 45 991569 100
40 31 32111 95
41 55 999454 100
42 57 986574 100
43 50 998946 100
43 32 9052 56
44 47 971000 100
45 47 996286 100
46 48 992880 100
47 49 998214 100
47 48 9722 22
47 40 11949 99
48 51 993624 100
49 52 987733 100
50 53 999340 100
51 69 985607 100
52 58 990186 100
53 54 994368 100
54 56 997336 100
55 57 978008 100
55 74 2656 20
55 49 8112 8
56 58 994638 100
56 45 6023 26
57 61 995621 100
57 58 13835 62
57 64 319 25
58 63 999422 100
59 63 994752 100
59 63 14488 92
59 61 7846 66
60 63 999151 100
60 62 10060 11
61 62 997286 100
61 64 5462 87
62 70 985629 100
63 64 995798 100
63 70 3473 66
64 67 991860 100
65 78 980655 100
65 70 6844 60
66 77 992487 100
67 68 999696 100
67 78 1315 74
68 69 987254 100
69 82 999648 100
70 76 999319 100
70 78 7137 44
71 80 999815 100
72 79 996796 100
72 82 19837 44
73 75 986094 100
73 81 7455 97
74 78 995200 100
75 83 961517 100
75 71 20162 17
76 82 996258 100
76 65 4135 86
76 68 14853 9
77 80 981025 100
77 67 4166 61
77 80 1578 99
78 84 995679 100
78 76 1184 39
79 80 998257 100
79 56 4377 20
80 84 992372 100
80 87 1723 86
81 90 999299 100
82 85 989245 100
83 84 964643 100
83 80 11804 3
84 90 999018 100
85 86 995022 100
85 82 6063 38
86 89 996507 100
87 89 978005 100
87 96 17780 73
88 92 962583 100
89 90 992760 100
90 91 993008 100
91 96 995137 100
92 93 993695 100
92 95 1219 53
93 96 999561 100
93 91 33692 11
94 99 990788 100
94 91 23197 79
95 103 990056 100
95 94 6070 48
95 91 11948 60
96 100 996538 100
97 98 988515 100
98 101 997383 100
98 96 6250 18
98 113 23699 2
98 97 16862 45
99 106 999698 100
99 103 18318 37
100 101 993112 100
100 89 4494 18
100 125 8509 79
100 108 17283 45
101 102 998269 100
102 107 997976 100
103 108 983386 100
104 111 993045 100
104 100 2744 44
104 95 10861 87
104 96 14968 77
104 103 2315 94
105 107 988307 100
105 110 10746 7
105 116 49 35
106 107 999813 100
106 112 5893 52
107 114 999127 100
107 101 11911 90
108 114 982266 100
108 116 6919 69
109 110 993011 100
110 116 996502 100
111 113 999685 100
112 116 997897 100
112 113 3460 62
113 114 996625 100
113 111 4553 93
113 121 17188 36
114 115 993629 100
115 116 998186 100
115 111 4826 45
115 125 2312 64
115 120 6410 83
116 120 996251 100
116 108 19666 81
117 135 996983 100
117 119 129 69
117 116 12215 23
118 119 992424 100
118 110 6000 30
118 120 14117 33
118 126 453 75
119 121 985652 100
119 121 37050 22
119 124 3906 1
120 132 981830 100
120 117 23966 86
121 123 986568 100
121 101 4404 39
121 109 779 79
122 125 996973 100
122 113 1801 12
123 124 968004 100
123 131 9278 76
124 128 990424 100
125 129 993033 100
126 135 990253 100
126 110 12729 24
126 119 3770 75
126 123 6493 44
127 135 998677 100
127 126 2253 83
127 126 7460 82
127 114 12352 51
128 135 990689 100
129 137 977791 100
129 132 4680 23
129 132 13495 34
130 135 987755 100
130 133 34439 16
131 136 995447 100
131 132 47623 41
132 134 997178 100
132 138 20708 25
133 139 955948 100
133 134 1273 57
134 135 997238 100
135 147 980643 100
136 139 995747 100
136 133 3787 42
136 148 12254 2
137 138 992604 100
137 132 5883 57
138 140 986207 100
138 136 2505 96
139 140 986922 100
140 141 988602 100
141 149 949966 100
142 144 992065 100
143 147 994732 100
143 146 3543 84
144 152 983220 100
144 142 656 83
144 160 8985 2
145 149 990044 100
145 148 18828 17
146 152 983556 100
146 142 14462 65
147 150 968867 100
147 138 213 62
148 151 979465 100
148 144 8791 23
149 157 990251 100
150 156 992172 100
150 148 28922 66
150 142 3737 88
150 154 4868 28
151 155 997717 100
151 149 303 59
152 155 985644 100
152 155 3091 13
152 150 9616 21
153 160 989740 100
153 158 159 15
154 155 994704 100
154 149 16003 12
155 156 996699 100
155 151 8706 69
155 158 26063 82
155 167 490 97
156 157 986268 100
157 158 991017 100
158 165 997488 100
158 163 1540 33
159 162 982083 100
159 153 4675 71
160 163 993958 100
161 166 989441 100
162 163 990778 100
163 168 994183 100
164 168 992917 100
165 166 984087 100
166 170 990798 100
166 168 2165 55
167 168 996360 100
167 169 23996 70
167 163 17452 76
168 172 995847 100
169 174 984411 100
170 174 993803 100
170 178 1913 63
170 168 10418 69
171 176 984038 100
171 173 14 48
172 179 992403 100
172 165 17668 63
173 182 969131 100
173 165 12743 73
173 171 32098 32
173 176 18767 34
174 177 989937 100
174 170 3450 99
175 177 993168 100
176 178 995240 100
177 180 992742 100
177 179 2408 18
178 179 992673 100
178 166 2918 13
179 181 971357 100
180 183 989868 100
181 185 983658 100
181 182 5286 35
182 183 976607 100
182 174 5630 56
183 184 990738 100
183 190 763 19
183 184 4285 38
183 181 3388 25
184 185 990582 100
184 186 6444 22
185 189 994013 100
185 173 3089 37
186 192 999605 100
186 187 11485 64
187 193 992476 100
187 186 132 28
187 186 11831 77
188 190 995511 100
188 185 11814 71
189 192 986899 100
190 192 986223 100
191 195 995855 100
191 189 3893 42
191 192 13410 74
191 193 2642 40
191 186 22716 72
192 194 996558 100
192 195 2099 87
192 189 3491 33
192 190 12709 97
193 199 994707 100
193 190 4186 30
193 225 3439 85
194 195 983203 100
194 190 10387 95
194 193 6202 100
195 197 954841 100
195 191 9172 44
196 198 999272 100
196 207 107 27
196 199 22965 33
197 198 985813 100
197 193 2711 66
197 196 2937 45
197 195 13245 86
198 200 999380 100
198 209 1243 18
198 200 3804 50
198 197 18051 96
199 206 992456 100
199 205 5518 14
199 193 5585 22
199 204 1240 47
200 206 999959 100
200 185 1362 15
200 201 14344 92
201 203 987819 100
201 184 15093 78
202 203 995801 100
202 206 3701 56
203 209 966785 100
203 199 2675 57
203 201 14728 32
204 210 986294 100
205 215 996802 100
205 208 503 86
206 208 984367 100
207 208 991065 100
208 209 988296 100
209 213 999567 100
209 208 4185 83
210 214 992635 100
210 223 294 6
210 215 10561 18
211 213 999470 100
211 214 1806 63
212 214 998897 100
212 205 3409 98
213 216 996488 100
213 220 22814 70
213 211 6176 85
214 215 993410 100
214 215 12821 18
215 216 994862 100
215 186 14018 26
216 219 983654 100
217 221 992114 100
218 219 993313 100
219 223 997375 100
219 221 6350 2
220 222 994421 100
220 219 13355 42
220 219 3940 22
220 218 11870 60
221 227 996722 100
221 222 3848 73
221 216 30260 60
222 226 989534 100
223 225 997733 100
224 229 998085 100
224 228 6268 91
224 223 17958 54
225 228 957693 100
225 224 1491 11
226 227 996246 100
226 223 11648 30
227 234 961018 100
228 229 998453 100
228 237 1389 33
228 227 13107 93
229 230 991838 100
229 226 6074 81
230 232 979290 100
230 224 5830 43
230 240 13047 91
230 233 13621 23
231 233 997205 100
231 239 34249 91
231 222 21977 33
232 233 999361 100
232 228 32001 47
233 241 997220 100
233 235 5045 59
233 223 12344 35
234 243 994206 100
234 243 18097 37
234 218 13916 65
235 239 969566 100
235 237 1060 63
235 232 6293 40
235 224 4518 62
236 241 995836 100
236 233 1934 40
237 241 989566 100
238 240 985453 100
238 236 2578 95
239 243 976493 100
239 238 2869 98
240 243 991370 100
240 243 918 100
241 245 975714 100
242 246 998998 100
243 244 982468 100
243 240 9355 43
244 245 978686 100
244 248 9736 88
245 246 981551 100
246 247 991883 100
247 248 994710 100
247 246 13645 47
247 251 2102 31
248 251 999666 100
248 247 11694 44
249 261 973021 100
250 251 998536 100
250 251 286 45
250 255 6638 96
250 246 6475 100
251 253 993914 100
251 262 897 73
251 244 28025 74
252 254 964411 100
252 249 1783 31
253 257 990197 100
253 254 13169 53
254 257 997849 100
255 256 999145 100
255 252 19987 9
255 252 2944 3
256 263 997665 100
257 262 991416 100
257 247 4469 20
258 262 997193 100
259 261 995721 100
260 262 997250 100
260 261 4740 87
261 262 989384 100
262 265 985986 100
263 264 994289 100
263 265 31588 74
264 265 998436 100
265 267 987046 100
266 271 990858 100
266 267 13775 33
267 273 995408 100
267 274 4713 57
268 269 998820 100
268 265 2852 56
268 262 5971 59
268 253 79 56
269 270 990967 100
269 274 213 47
269 281 5246 93
270 273 962238 100
270 263 271 87
270 272 14593 27
271 277 997284 100
271 267 4470 58
272 276 992188 100
272 270 11611 75
272 265 7513 28
272 277 8135 81
272 270 12781 13
273 277 999375 100
274 278 997340 100
274 263 16313 25
275 283 997752 100
275 274 11246 69
275 272 22372 13
276 278 995185 100
276 275 5804 60
276 277 9786 2
276 280 11495 3
277 278 986542 100
278 280 983499 100
278 283 722 8
279 281 994776 100
279 273 3885 3
280 291 994942 100
280 281 1193 37
281 288 995209 100
281 297 4202 29
281 274 14037 87
282 283 998759 100
282 291 7053 30
283 284 980714 100
284 285 992877 100
285 288 968213 100
285 276 24422 27
286 287 997698 100
286 280 16519 94
287 289 997016 100
287 293 7129 92
287 283 5879 37
288 290 994526 100
288 294 4085 10
289 293 988639 100
289 285 363 43
290 293 996701 100
290 292 8430 10
291 295 980572 100
292 295 990692 100
293 295 998666 100
293 279 29413 91
294 297 981430 100
295 296 974537 100
295 309 2680 49
295 283 9835 35
295 291 12766 2
296 298 933647 100
297 305 994468 100
297 299 14468 40
298 299 998490 100
298 293 2486 3
298 303 1721 91
299 300 994546 100
299 319 158 96
299 301 1872 65
300 304 995663 100
300 301 1210 42
301 309 988339 100
302 304 990480 100
302 303 9519 47
302 293 9732 59
303 304 985938 100
303 289 16726 99
303 302 2074 94
304 305 996642 100
305 307 975554 100
305 312 6417 25
306 308 976474 100
306 298 5164 89
306 303 1078 29
307 308 994285 100
307 315 3030 90
308 317 990356 100
308 315 12544 46
309 314 996500 100
309 305 9409 60
310 312 984756 100
310 312 2793 38
310 289 495 42
311 315 991386 100
311 304 4433 90
311 313 15548 33
312 313 996043 100
312 309 6145 25
312 313 6800 66
312 314 2594 15
313 315 991983 100
313 315 902 23
314 316 999662 100
314 315 3519 69
315 317 993321 100
315 317 11689 16
315 316 18430 46
315 316 5724 98
316 318 948307 100
316 315 8259 58
317 318 986784 100
317 315 8567 51
318 322 997393 100
319 324 999631 100
319 307 5511 44
319 317 16039 68
320 326 986960 100
321 322 989950 100
322 323 999671 100
322 321 33034 29
323 325 999443 100
323 321 23829 95
324 325 995583 100
325 326 990136 100
326 327 998656 100
326 317 531 46
327 328 998308 100
327 328 4831 61
328 329 987770 100
329 330 987690 100
329 324 3131 14
330 332 982029 100
330 323 3120 99
331 336 977883 100
331 334 29088 55
332 336 999644 100
332 333 15189 39
333 334 998667 100
333 336 4394 45
333 346 8919 53
334 336 988477 100
334 331 13432 39
334 336 9023 80
335 336 998642 100
336 337 998244 100
337 338 995056 100
338 339 991412 100
338 346 15270 62
339 341 991222 100
340 341 985622 100
340 345 11855 62
340 339 1452 58
341 342 997127 100
342 345 998514 100
343 350 993074 100
343 348 5577 63
344 345 998648 100
345 346 998638 100
346 349 996114 100
347 348 989308 100
347 338 5044 96
347 344 6773 16
347 348 442 47
348 349 976611 100
348 350 19447 96
348 340 7226 63
348 345 4020 3
349 350 999089 100
349 353 6428 41
350 352 991551 100
351 353 998419 100
352 356 991594 100
352 354 719 37
353 355 992320 100
353 365 8215 98
354 356 995818 100
355 358 983856 100
355 353 11690 10
355 360 16814 50
356 357 991560 100
357 358 996968 100
357 363 16042 32
357 356 1451 16
358 363 998764 100
358 362 5504 48
358 350 6656 60
359 360 989176 100
360 361 992830 100
360 353 2002 49
361 362 998891 100
361 360 14434 96
362 364 988063 100
362 380 14395 49
363 365 999636 100
363 355 16146 37
364 365 990474 100
364 367 12618 6
364 365 8637 63
364 368 7117 22
364 366 36088 26
364 365 9886 26
365 366 986906 100
366 367 996374 100
366 367 29163 60
366 353 1605 77
367 368 998347 100
368 369 988105 100
368 378 3094 19
369 370 978431 100
370 374 990932 100
371 372 970238 100
372 373 994349 100
372 365 4037 60
372 373 121 75
373 374 995939 100
373 379 2436 16
374 375 992559 100
374 375 18946 92
375 376 995230 100
375 369 3516 20
375 379 14859 18
376 377 979541 100
376 370 3523 24
377 379 992588 100
377 381 36519 6
377 371 18184 81
378 381 960317 100
379 380 998166 100
379 376 25601 44
380 382 999870 100
380 379 2564 82
380 387 7172 51
380 378 2074 67
381 383 984922 100
382 383 990602 100
383 386 997043 100
384 389 998728 100
384 385 16896 36
384 389 292 63
384 383 2930 86
385 386 996039 100
386 387 999404 100
386 379 593 27
386 382 15618 1
387 388 987325 100
387 383 15279 67
387 388 9941 72
388 390 988444 100
388 387 20816 65
388 394 1783 93
389 395 993328 100
389 388 6187 68
389 384 7650 30
390 391 994340 100
390 382 2081 31
391 393 998408 100
392 393 999436 100
392 383 26489 73
393 395 990965 100
393 392 2007 60
394 395 983287 100
394 387 12737 74
395 396 988681 100
395 394 2192 47
395 390 2773 57
396 397 983666 100
396 390 30371 94
396 397 309 32
397 398 999150 100
397 387 1906 43
398 402 999139 100
398 402 3940 91
398 401 1207 74
398 389 16265 98
399 402 999820 100
400 403 996680 100
401 402 997439 100
401 409 1196 36
401 406 8232 93
401 389 4204 44
402 403 997511 100
403 407 997225 100
404 405 995378 100
404 405 7290 52
405 406 998751 100
405 412 7423 86
406 407 981685 100
406 407 7106 89
407 408 988368 100
408 409 989444 100
408 411 5102 83
409 411 996079 100
409 407 7215 44
409 417 10186 62
410 411 995610 100
411 414 998834 100
412 413 999626 100
412 421 2403 100
413 414 970429 100
413 421 3320 21
414 417 994473 100
414 416 7484 27
415 416 982342 100
415 417 7633 40
416 420 996957 100
417 419 977914 100
417 414 9355 4
418 419 988230 100
418 419 9628 43
419 421 991913 100
419 424 5227 17
420 421 990439 100
420 416 3300 58
421 426 992060 100
422 424 999363 100
422 417 10016 62
422 420 1215 54
423 424 994573 100
423 413 5161 87
424 425 991732 100
424 427 2945 46
425 426 967333 100
425 412 3455 21
425 422 2218 71
426 427 985908 100
426 419 4206 31
427 428 990078 100
427 441 7639 94
428 429 994226 100
429 430 999877 100
429 423 1636 26
429 435 581 70
430 431 998732 100
430 447 37572 33
430 434 11473 42
431 435 994187 100
431 435 10288 35
432 433 967505 100
432 428 1050 82
433 434 999893 100
433 439 2187 97
434 436 946727 100
434 440 6132 60
435 436 991907 100
435 426 464 5
436 438 982733 100
436 431 11931 38
437 438 998064 100
437 431 13441 85
438 439 990815 100
438 424 3695 28
438 436 18456 66
438 429 7310 84
438 436 43 72
439 441 979974 100
439 440 1257 84
439 444 15556 30
440 441 999876 100
440 435 19021 14
441 442 993483 100
442 443 992094 100
443 444 973976 100
443 435 3261 1
443 441 16911 62
444 445 999722 100
444 447 8720 74
445 446 998746 100
445 449 487 59
445 447 79 97
446 447 998852 100
447 448 988116 100
447 448 34376 27
448 449 997478 100
448 450 13149 10
449 450 994437 100
449 446 5248 64
449 453 29693 87
450 451 991322 100
450 432 9687 41
451 452 966968 100
452 453 994108 100
452 457 9574 81
452 453 11052 32
453 454 972654 100
454 455 991306 100
455 456 998320 100
455 457 2602 6
455 454 9185 93
456 457 999344 100
456 453 1699 100
456 452 7377 3
456 453 20595 42
457 458 978895 100
457 452 856 10
458 460 993839 100
458 442 1077 47
459 460 997370 100
460 461 995652 100
460 459 3079 98
460 459 7353 23
461 462 990558 100
461 460 100 51
462 464 994629 100
462 475 12767 14
462 459 3395 44
463 464 988208 100
463 461 15721 100
464 465 997570 100
464 472 13718 29
464 462 13360 47
465 466 992497 100
465 466 551 80
465 458 6198 48
466 467 993080 100
467 468 975270 100
467 465 4829 27
468 469 997233 100
469 470 999421 100
469 462 1662 75
469 472 666 73
470 471 985678 100
471 472 992437 100
471 467 3934 20
472 473 998215 100
472 480 11637 18
473 474 992832 100
474 475 996223 100
475 476 999238 100
476 477 997706 100
477 478 998901 100
477 469 11246 84
478 479 994140 100
478 479 10354 5
478 476 10577 43
479 480 997970 100
480 481 949597 100
480 478 2852 89
481 482 977040 100
481 484 11788 98
481 488 15143 29
481 479 4748 30
481 487 24009 6
482 483 997417 100
482 484 3034 46
482 484 4370 8
483 484 992692 100
483 479 2550 74
484 485 980232 100
485 486 998033 100
485 482 20750 17
486 487 985857 100
486 484 3945 92
487 488 990644 100
487 485 10264 91
488 489 997853 100
488 494 4868 69
488 500 2442 69
489 490 995111 100
489 483 13151 57
489 492 21 27
490 491 997499 100
491 492 977641 100
491 483 2058 18
492 493 941196 100
492 486 2462 17
493 494 967510 100
493 497 2966 7
494 495 997628 100
494 496 9692 99
495 496 994475 100
495 490 9870 59
496 497 989723 100
496 495 3162 22
497 498 971751 100
497 493 8622 65
498 499 999876 100
498 500 11724 1
498 495 5462 8
499 500 965896 100
499 500 362 86
