8
500 1000 1000
105420000000 122380000000
1 4 951126 100
1 14 326138 80
1 27 104611 64
2 3 850080 100
2 4 338058 26
2 1 13835 28
3 4 986609 100
3 17 452872 13
4 7 978570 100
5 6 949125 100
5 10 20545 21
6 11 984353 100
7 8 993334 100
7 12 7186 21
8 18 939896 100
8 16 120301 17
9 10 950091 100
9 1 66476 3
10 13 999527 100
11 13 954340 100
11 24 6981 71
11 10 104148 96
11 7 5323 57
12 13 976511 100
12 11 43786 66
12 11 60070 58
12 1 5836 93
13 14 986780 100
13 7 3441 48
14 15 945009 100
15 16 946289 100
16 19 966446 100
16 5 46989 19
16 10 22303 12
17 18 964409 100
18 22 983448 100
19 21 909051 100
19 25 81196 61
20 22 996124 100
20 37 316830 74
21 22 967455 100
22 24 968164 100
23 29 890093 100
23 15 246479 81
23 19 42305 32
24 25 952163 100
24 17 57205 78
25 27 967972 100
25 9 16879 57
26 31 908090 100
26 25 81165 51
27 28 954374 100
27 17 105026 79
27 24 63989 80
28 36 949835 100
29 31 977152 100
30 31 945639 100
30 31 25333 54
31 36 993843 100
32 33 972845 100
32 17 42644 52
32 10 102543 94
33 35 989659 100
33 37 9248 16
33 45 58583 8
33 28 95020 90
34 39 986117 100
35 37 966373 100
36 39 991462 100
36 50 6026 39
36 30 32457 47
36 28 3771 19
37 38 986607 100
38 39 937415 100
39 40 985197 100
39 35 257592 74
39 37 293034 83
40 45 986068 100
41 44 985755 100
42 43 999985 100
42 40 58459 58
42 37 50033 36
43 46 924501 100
43 42 21786 1
44 45 908294 100
45 46 849785 100
45 47 101487 41
46 54 909657 100
47 49 981513 100
47 48 132399 17
47 44 112759 45
48 51 894491 100
49 54 993465 100
50 51 969058 100
50 57 394379 92
51 52 989131 100
52 53 980261 100
52 61 113071 55
53 64 980726 100
53 50 75879 20
54 57 997198 100
54 58 259789 10
54 68 63323 47
55 60 994856 100
56 57 996692 100
57 59 981237 100
58 63 998412 100
58 48 9448 78
59 62 934987 100
59 67 432062 65
60 69 966331 100
61 63 990618 100
62 64 875146 100
63 64 992247 100
63 67 10647 25
63 68 144883 92
63 61 313150 91
63 51 34054 72
64 66 940427 100
64 63 5377 1
65 69 957564 100
66 73 993156 100
66 87 48252 46
66 67 7044 63
67 73 946462 100
67 77 246633 79
68 70 968462 100
69 71 992203 100
69 74 155440 79
70 73 980547 100
70 82 45254 1
71 73 991758 100
71 65 10419 6
72 74 991972 100
73 75 972025 100
73 70 32656 7
73 68 38540 23
74 77 955965 100
74 71 38716 70
75 79 952946 100
75 69 46920 76
76 78 962683 100
76 72 2912 32
76 71 151611 88
76 61 110052 85
76 75 44232 9
77 79 976686 100
77 76 99546 47
77 73 40324 69
78 81 964913 100
78 79 47604 80
79 80 914692 100
79 82 76795 13
79 70 103218 61
80 81 937515 100
80 46 23400 37
81 85 976686 100
82 84 740646 100
82 86 172901 84
83 84 971062 100
84 93 969397 100
84 88 152562 30
85 86 973128 100
86 87 992669 100
86 97 385395 64
86 94 84038 6
87 88 983457 100
87 88 308712 85
87 80 109058 61
88 92 923961 100
88 80 543344 91
88 82 49049 47
88 85 27790 43
88 85 8285 35
89 90 922844 100
90 93 956780 100
90 80 254879 72
91 93 980969 100
92 93 907375 100
92 104 269310 28
93 94 969818 100
93 110 176072 12
93 83 48250 36
94 96 990001 100
94 90 27262 66
95 99 991426 100
96 97 977029 100
97 98 957483 100
97 91 18442 12
98 99 983519 100
99 102 973175 100
99 102 7557 10
99 104 8977 2
100 102 908069 100
100 102 155244 52
100 103 32049 37
101 106 859194 100
101 104 31646 54
102 104 933254 100
102 100 106305 6
102 79 107818 54
103 111 974930 100
103 98 116886 26
104 105 975070 100
104 123 247433 37
104 99 19305 58
104 102 24352 59
105 115 999143 100
106 108 966842 100
107 109 998581 100
108 110 994303 100
108 120 48263 46
108 109 441246 91
109 115 893449 100
109 108 24564 6
110 116 978810 100
111 112 962309 100
111 87 29845 61
112 116 980234 100
112 114 400834 92
112 116 119025 59
112 121 25809 90
113 116 979367 100
113 124 180828 93
113 114 127204 45
113 120 493853 73
114 116 995506 100
115 116 899705 100
115 118 192256 63
115 108 2830 90
115 100 227811 83
116 118 996600 100
116 113 8525 1
116 107 9591 70
117 118 973104 100
117 119 185505 76
117 107 631 52
118 124 989608 100
119 123 973133 100
119 115 84767 29
120 121 826087 100
120 110 108706 48
121 123 928420 100
122 123 974352 100
122 138 126336 73
122 135 104417 79
123 124 960670 100
124 125 998556 100
124 121 24568 7
125 131 961329 100
126 128 967172 100
126 137 358119 75
126 134 17362 29
127 129 971175 100
127 121 207435 67
128 134 960449 100
128 122 6831 43
129 133 936605 100
129 143 355479 48
129 130 71871 99
130 132 966739 100
131 132 927320 100
131 138 42577 12
131 120 49665 64
132 133 981716 100
132 140 663802 86
132 129 27982 48
133 134 980826 100
133 139 85274 69
134 135 937207 100
135 138 753171 100
135 108 60207 4
135 116 56705 14
136 138 950050 100
137 139 919980 100
137 156 247523 75
138 139 885741 100
139 140 947837 100
139 135 103072 88
140 142 973569 100
141 142 992224 100
141 131 23615 14
141 131 415390 98
142 144 992967 100
143 144 989654 100
144 145 979859 100
144 160 3354 17
145 146 975025 100
145 143 40186 71
146 149 953632 100
147 151 973950 100
148 149 945814 100
148 150 51967 20
149 151 941271 100
149 144 7297 62
149 133 173900 57
150 152 988604 100
151 152 904794 100
151 147 88706 37
152 154 989642 100
152 157 54955 12
152 154 16343 35
153 155 929256 100
153 151 4956 52
154 155 997032 100
155 156 986151 100
155 138 52665 6
155 144 24714 34
156 159 994792 100
156 148 45833 100
157 158 881571 100
158 160 941356 100
158 163 15303 14
159 160 969804 100
159 150 203022 91
160 161 985606 100
161 166 996554 100
161 175 26991 4
161 169 49767 82
162 167 931562 100
163 165 908968 100
163 160 11323 18
164 167 984932 100
164 162 62342 34
165 168 993522 100
165 178 23992 39
165 154 9399 53
166 169 975851 100
166 157 98960 75
167 171 983230 100
168 170 960712 100
168 174 2027 73
168 171 185706 97
169 174 990174 100
169 181 445908 67
169 178 14687 16
170 175 923629 100
171 172 930509 100
171 172 78612 37
171 174 665721 84
172 175 968037 100
173 174 971124 100
174 175 974557 100
174 184 2226 50
175 177 995309 100
175 176 34416 25
176 178 979023 100
177 180 978414 100
177 175 34688 16
178 184 934344 100
178 186 595391 90
179 181 954210 100
179 181 241134 42
179 175 5708 26
179 161 44245 4
180 181 962741 100
180 184 70585 32
181 182 989721 100
181 176 26794 95
182 184 972164 100
183 190 971410 100
183 169 24781 26
184 186 885701 100
184 213 36595 84
184 185 609883 71
184 190 27527 29
184 189 3208 87
184 186 5579 59
185 189 953311 100
185 181 148375 98
186 188 947296 100
186 187 175121 3
186 178 133131 63
186 184 8687 24
186 175 15115 8
186 184 177540 83
187 190 927494 100
187 193 61008 62
188 193 996914 100
188 190 198576 18
189 192 984919 100
189 188 52104 90
189 172 22796 12
189 181 73495 19
190 191 977212 100
190 198 1253 41
190 209 67633 64
191 197 926600 100
192 196 965474 100
192 219 1796 32
192 200 22786 7
193 196 996606 100
194 195 880636 100
194 195 149935 67
194 214 69910 40
194 190 3448 42
195 196 859872 100
195 175 25921 64
196 201 993218 100
196 186 80657 86
197 199 979305 100
197 191 204674 97
198 210 981160 100
198 195 35666 8
198 195 715585 91
199 200 954843 100
199 196 30401 56
200 201 958075 100
200 181 4238 4
200 192 37276 11
201 203 956050 100
202 210 985227 100
203 204 843065 100
203 230 98301 30
203 183 44500 16
204 206 956180 100
204 198 19502 76
205 208 977485 100
205 210 268627 93
205 204 72207 38
206 207 970922 100
206 205 39377 59
207 208 972906 100
208 219 993044 100
208 214 208842 6
208 209 159582 93
208 199 56450 47
209 211 974598 100
210 214 932078 100
211 215 962278 100
211 220 57424 16
212 215 914017 100
212 186 102204 52
213 215 870522 100
213 210 25675 75
214 221 972876 100
214 210 81771 67
215 216 946909 100
215 213 19863 56
216 217 972894 100
217 220 998095 100
217 219 154874 89
217 234 171899 58
217 218 215155 32
218 219 943087 100
219 220 980494 100
219 202 23954 8
220 223 937571 100
221 223 909689 100
222 223 794785 100
222 208 208603 92
222 209 15360 46
223 225 987632 100
223 225 78942 27
224 225 992385 100
224 219 91661 88
224 215 22535 85
225 227 996231 100
225 223 8632 67
225 216 33847 12
226 229 988955 100
226 229 321387 49
227 234 873674 100
227 235 86180 72
228 230 972105 100
228 249 130340 98
229 232 987362 100
229 222 7963 2
230 233 998167 100
230 223 85038 83
231 240 872411 100
231 245 37756 19
232 235 995064 100
232 235 30649 28
233 234 989839 100
233 227 169792 81
233 228 43184 71
234 235 953817 100
234 236 263476 24
234 231 365954 91
235 241 980260 100
235 236 433445 89
235 236 826137 94
236 239 981532 100
236 237 85784 19
236 235 31949 49
237 239 927268 100
237 244 390553 67
237 236 43790 73
238 239 967282 100
239 243 998585 100
240 241 985561 100
240 251 75792 49
241 245 891479 100
241 244 15232 10
242 245 987526 100
242 236 4196 81
243 244 936295 100
244 245 981516 100
244 243 191901 88
245 246 990291 100
245 238 14457 17
246 247 932318 100
246 239 509 25
247 253 966560 100
247 227 8257 1
247 241 289212 85
248 250 934386 100
248 249 27697 27
248 271 236307 59
249 250 976049 100
250 260 916882 100
251 258 972220 100
252 254 920321 100
253 254 916501 100
253 268 40986 4
253 252 35476 9
253 247 75770 49
254 255 988408 100
255 258 974716 100
255 241 13677 74
255 246 231229 79
255 251 25371 21
256 257 931150 100
256 236 31612 31
257 258 956079 100
257 268 291096 98
258 259 943792 100
258 261 243248 1
259 262 976317 100
260 261 987347 100
260 254 29430 45
261 263 873538 100
262 263 962674 100
263 265 990537 100
264 266 988095 100
265 269 963331 100
266 271 958076 100
267 268 972309 100
267 281 35411 49
267 278 116362 72
268 274 981721 100
269 270 916901 100
269 285 41567 1
270 274 970174 100
270 269 43335 79
271 277 962428 100
271 265 11890 83
272 274 997172 100
272 266 164220 100
272 271 15350 31
273 275 974163 100
274 282 934492 100
275 276 954455 100
275 281 293926 24
275 269 13999 71
276 277 998683 100
276 272 10130 57
276 274 6182 2
276 270 3564 78
277 278 985688 100
278 283 976662 100
278 283 30386 48
278 289 87619 79
278 275 31306 12
278 276 28511 30
278 268 148884 92
279 284 931235 100
280 285 976391 100
281 289 996455 100
282 283 994322 100
283 286 969556 100
284 289 930244 100
284 266 18634 75
285 287 942302 100
286 288 985062 100
286 287 1536 40
287 289 970870 100
288 291 996501 100
288 276 80596 61
288 270 37868 23
289 290 990390 100
290 291 933593 100
291 295 972605 100
291 285 15490 18
292 293 932860 100
292 289 22618 37
293 295 857335 100
294 298 976766 100
294 303 104600 29
294 282 35221 55
295 297 804403 100
295 305 451112 74
295 320 143831 38
296 297 970651 100
297 300 905750 100
297 314 296164 3
297 302 222393 17
298 300 968287 100
299 301 995491 100
300 302 838607 100
300 305 350170 42
301 302 978190 100
302 304 973818 100
302 297 104733 79
302 298 77586 90
303 305 982876 100
304 305 894412 100
305 306 896314 100
305 307 21668 13
306 307 987321 100
306 296 45153 57
307 310 992435 100
307 305 107250 41
308 309 939111 100
308 298 14516 80
308 305 280656 69
308 305 7909 11
308 306 15897 62
309 310 955985 100
310 314 954917 100
311 312 992704 100
311 308 664 29
311 305 248448 100
312 322 959166 100
313 317 935690 100
313 315 861742 100
313 319 173985 19
314 316 856608 100
314 332 21256 95
314 318 33059 51
314 313 184 26
315 316 962450 100
315 302 460260 98
316 317 940153 100
316 320 208985 36
317 318 916672 100
318 319 988765 100
318 327 26337 100
318 321 265131 61
318 307 83374 97
319 322 915161 100
320 327 912353 100
321 323 954763 100
321 334 132551 84
321 314 108917 48
321 312 302093 95
322 324 999990 100
322 324 287381 74
322 333 20436 7
323 325 939339 100
324 330 984098 100
325 327 982059 100
325 350 186744 68
326 327 997581 100
327 330 988989 100
328 329 974171 100
329 330 995368 100
329 313 74907 83
330 331 973860 100
331 332 899435 100
331 314 23514 33
332 333 939543 100
332 342 183472 24
332 336 233240 31
332 326 225733 59
333 335 880935 100
333 335 7666 22
334 336 993796 100
335 340 985345 100
335 321 95269 89
336 338 896469 100
336 337 34214 26
336 332 5667 7
336 334 25681 11
337 341 943618 100
337 343 168553 2
337 334 80528 83
338 341 975547 100
339 353 920974 100
339 361 179315 99
339 333 25461 6
339 337 40449 57
340 341 994394 100
340 355 69915 49
340 322 17599 87
341 346 973991 100
342 343 907953 100
343 348 856607 100
343 334 45649 82
343 342 25539 12
344 349 982313 100
345 347 989312 100
346 352 994220 100
346 337 29695 57
346 345 125989 43
347 348 845419 100
348 351 990862 100
348 333 5325 19
349 351 940445 100
350 351 806066 100
350 356 140934 68
350 359 402464 95
351 352 906448 100
351 354 265669 83
351 353 206507 100
351 353 49688 53
352 354 908581 100
352 351 2287 29
353 356 992219 100
353 374 190280 82
354 355 973015 100
354 362 163534 53
355 360 917150 100
356 360 994096 100
356 350 59853 3
357 358 958243 100
357 342 30037 26
357 353 7714 58
358 360 962286 100
358 375 61205 90
359 360 965690 100
359 346 12632 59
359 344 33996 18
359 355 10317 3
360 361 989890 100
360 351 462167 99
361 369 942100 100
361 385 63173 14
361 359 1724 28
362 367 953337 100
362 375 45684 65
363 367 982109 100
364 365 923478 100
364 372 386471 50
364 362 315236 99
365 367 845193 100
365 383 16187 20
365 370 236243 78
366 368 997407 100
367 369 958210 100
367 368 446997 90
367 359 83069 84
368 371 990499 100
368 372 80094 44
369 371 982667 100
370 371 993497 100
371 374 954352 100
371 377 126601 18
372 375 999965 100
373 374 927800 100
373 381 52757 10
373 378 139258 82
374 375 923744 100
375 377 995565 100
376 378 962649 100
377 378 979294 100
378 379 902850 100
378 374 153877 96
379 380 990038 100
380 381 976333 100
381 382 993856 100
381 370 95626 66
382 383 894488 100
382 386 80739 84
383 384 983312 100
384 385 954445 100
384 405 100701 15
384 378 366121 96
385 386 857123 100
385 377 169454 72
386 392 974373 100
387 388 852923 100
388 389 980545 100
388 391 112249 3
389 393 997494 100
389 378 41876 63
390 392 918107 100
391 392 936536 100
391 396 194635 12
392 393 970706 100
392 386 32945 25
392 388 16285 21
392 372 101580 60
393 397 968486 100
393 387 91189 64
393 391 88973 77
394 396 935831 100
394 396 37453 4
394 393 102171 7
395 398 950153 100
396 397 952130 100
397 400 949064 100
397 398 254631 63
397 391 61730 72
398 400 951244 100
398 373 37234 36
399 400 996947 100
400 401 986486 100
401 403 951605 100
401 410 147546 19
402 406 917409 100
402 404 45745 38
403 407 988739 100
404 405 998142 100
405 408 859353 100
406 407 942587 100
406 410 171004 83
406 413 89452 40
407 417 861350 100
408 413 929761 100
408 404 27774 49
409 410 922013 100
409 399 34364 77
409 392 63687 43
410 414 990118 100
411 413 909707 100
411 406 225813 80
412 414 970980 100
413 415 816029 100
413 414 35 41
413 409 12919 1
413 402 28528 19
414 419 918181 100
415 416 971204 100
416 425 995330 100
416 415 68273 95
416 410 11522 41
416 414 16252 66
416 414 17121 33
417 419 945377 100
417 409 14117 43
418 420 977959 100
418 420 141590 8
418 419 268708 72
418 419 290448 84
419 422 958769 100
419 433 184733 16
420 421 988360 100
421 424 989549 100
422 424 997093 100
423 426 987646 100
423 418 50971 14
424 429 944265 100
425 426 974367 100
425 429 348435 59
425 422 27858 53
426 431 917991 100
426 422 39140 60
427 429 955870 100
427 426 23257 55
428 433 992450 100
428 429 111387 59
429 430 984345 100
429 435 133677 61
430 437 935260 100
430 429 79191 13
431 434 983476 100
432 436 920608 100
432 429 37375 50
432 417 12559 49
432 414 26413 67
432 419 2748 2
433 437 924127 100
433 450 45613 5
434 440 918040 100
434 436 95192 25
435 437 948945 100
436 438 919791 100
437 440 923008 100
437 443 277958 46
438 439 991859 100
438 414 62753 49
439 443 847348 100
439 437 88246 41
440 442 982094 100
441 446 997505 100
441 446 150614 56
442 444 892286 100
442 438 29331 26
443 445 977805 100
443 446 140904 33
444 446 994871 100
444 438 40205 8
445 447 884478 100
446 448 923004 100
446 448 155214 95
447 448 993647 100
447 449 84446 37
448 451 976644 100
448 443 193831 66
449 453 931738 100
449 427 35524 62
449 444 156528 85
450 453 972043 100
451 453 945587 100
451 433 5024 64
451 441 64831 15
452 459 994024 100
453 456 931072 100
454 455 931593 100
454 486 10662 24
454 463 51027 31
454 444 38893 23
454 453 54008 3
455 458 908056 100
455 453 15515 14
455 450 101054 59
456 460 990259 100
456 463 107134 91
456 442 60392 72
457 462 993930 100
458 462 970576 100
459 461 705942 100
459 480 111244 23
460 464 994393 100
460 466 148502 32
461 464 948734 100
462 464 883411 100
463 465 964879 100
463 471 32905 48
464 465 943242 100
464 456 2165 17
464 462 70937 24
465 467 998339 100
465 470 192575 43
466 470 997335 100
466 470 246071 32
466 463 37868 11
466 463 78209 21
467 469 978953 100
468 471 999389 100
469 470 986971 100
469 495 153021 54
469 474 257970 44
470 480 985118 100
470 482 41642 34
471 473 998991 100
471 477 33025 48
471 466 635062 84
471 464 194967 91
472 474 909024 100
472 462 15801 59
473 475 996294 100
473 481 262370 99
474 475 907055 100
474 487 809 78
474 459 209061 81
475 484 888064 100
475 496 43164 12
476 478 935458 100
477 481 990151 100
477 473 47910 64
477 473 57819 1
478 481 929730 100
478 481 111171 31
478 490 94599 60
479 483 971710 100
480 481 996208 100
481 482 933945 100
481 489 480843 56
481 494 32224 17
481 480 20818 2
482 484 999790 100
482 473 22625 12
483 486 899246 100
484 486 998496 100
484 479 46408 78
485 491 999380 100
485 492 12580 25
486 487 964632 100
487 491 973485 100
487 500 44118 32
487 478 454957 97
487 478 21347 78
488 493 924635 100
488 475 20724 39
488 482 44774 85
488 473 41250 2
488 470 63034 37
489 490 977348 100
490 496 914392 100
491 496 985276 100
491 496 186287 58
492 493 958370 100
492 498 245674 39
493 494 981836 100
494 498 980146 100
494 492 61277 69
495 497 880515 100
495 490 3543 12
496 498 809243 100
497 500 937641 100
497 478 7859 39
497 496 59599 50
498 499 993765 100
499 500 986289 100
499 500 183142 33
499 485 43132 90
499 485 203665 80
