1000 1000
1 2 127
2 3 854
1 4 813
4 5 8
5 6 74
6 7 290
3 8 408
8 9 570
9 10 848
3 11 852
2 12 163
7 13 494
9 14 982
4 15 835
12 16 125
15 17 33
6 18 119
8 19 732
17 20 115
12 21 155
1 22 775
9 23 960
18 24 136
4 25 943
10 26 656
2 27 253
5 28 683
10 29 90
10 30 4
17 31 178
12 32 904
6 33 226
11 34 692
12 35 126
25 36 99
18 37 449
20 38 895
25 39 738
35 40 825
22 41 50
38 42 317
31 43 94
18 44 56
24 45 699
21 46 590
42 47 529
23 48 217
2 49 275
38 50 37
7 51 621
24 52 619
17 53 197
1 54 321
40 55 67
13 56 955
3 57 685
50 58 614
7 59 642
58 60 89
14 61 99
44 62 689
17 63 645
43 64 382
17 65 813
57 66 962
48 67 646
31 68 675
10 69 482
46 70 45
14 71 45
20 72 92
9 73 724
20 74 619
21 75 725
55 76 806
21 77 253
37 78 660
57 79 849
14 80 254
57 81 309
30 82 313
34 83 458
82 84 658
32 85 802
44 86 433
6 87 36
57 88 548
69 89 338
17 90 881
19 91 266
26 92 29
55 93 237
61 94 208
69 95 222
85 96 23
24 97 853
74 98 353
46 99 677
65 100 279
28 101 314
15 102 579
45 103 603
79 104 354
6 105 673
26 106 248
33 107 803
27 108 310
9 109 85
74 110 146
50 111 737
101 112 426
85 113 272
46 114 555
106 115 115
97 116 321
51 117 243
20 118 268
38 119 429
98 120 772
96 121 101
16 122 71
28 123 651
115 124 79
98 125 456
84 126 57
71 127 109
51 128 677
51 129 178
5 130 787
111 131 893
38 132 479
78 133 834
65 134 211
15 135 708
22 136 185
65 137 896
55 138 140
24 139 638
124 140 71
77 141 546
23 142 142
15 143 963
127 144 591
67 145 388
66 146 458
127 147 552
73 148 39
15 149 800
25 150 533
33 151 924
24 152 394
78 153 398
100 154 344
67 155 319
86 156 93
102 157 709
45 158 214
103 159 80
128 160 335
78 161 307
46 162 687
129 163 965
103 164 602
164 165 393
104 166 371
75 167 392
9 168 500
142 169 74
32 170 281
34 171 656
127 172 633
113 173 517
160 174 153
16 175 486
109 176 541
78 177 712
47 178 600
89 179 913
143 180 589
83 181 472
159 182 907
61 183 275
176 184 742
13 185 574
73 186 638
10 187 221
101 188 705
124 189 628
147 190 262
78 191 984
52 192 950
127 193 768
144 194 60
60 195 373
88 196 656
51 197 128
123 198 492
53 199 840
156 200 344
121 201 846
6 202 574
151 203 320
125 204 909
48 205 205
157 206 883
73 207 185
178 208 434
177 209 477
68 210 859
10 211 734
143 212 289
184 213 179
36 214 493
188 215 209
74 216 216
16 217 245
26 218 119
5 219 157
91 220 194
59 221 452
141 222 912
107 223 117
44 224 729
80 225 122
130 226 891
153 227 733
180 228 273
223 229 22
136 230 910
8 231 794
226 232 383
222 233 717
1 234 682
132 235 974
34 236 33
42 237 931
192 238 388
50 239 262
74 240 216
186 241 851
34 242 532
211 243 63
122 244 493
49 245 627
102 246 828
4 247 198
25 248 929
27 249 442
209 250 196
87 251 422
223 252 121
208 253 934
214 254 733
80 255 88
185 256 72
171 257 897
66 258 172
53 259 214
239 260 629
163 261 524
22 262 792
157 263 207
8 264 280
218 265 431
137 266 414
233 267 986
64 268 584
164 269 631
35 270 979
61 271 28
213 272 263
227 273 769
120 274 995
157 275 556
163 276 801
144 277 237
109 278 944
97 279 754
176 280 96
9 281 238
31 282 837
217 283 154
64 284 157
274 285 489
79 286 613
125 287 295
237 288 931
62 289 132
188 290 591
156 291 182
157 292 53
160 293 401
264 294 235
114 295 528
78 296 99
239 297 403
223 298 770
97 299 292
35 300 527
194 301 744
61 302 90
103 303 331
150 304 205
42 305 63
134 306 359
64 307 749
128 308 747
49 309 564
202 310 673
141 311 812
184 312 374
120 313 713
112 314 930
33 315 336
16 316 382
258 317 438
101 318 704
272 319 723
267 320 203
244 321 364
108 322 899
78 323 758
100 324 505
69 325 983
263 326 632
301 327 595
113 328 968
202 329 2
142 330 894
188 331 308
218 332 1000
191 333 863
60 334 783
195 335 931
2 336 396
154 337 166
159 338 674
130 339 419
144 340 573
69 341 757
204 342 687
297 343 798
210 344 578
291 345 314
201 346 715
273 347 240
169 348 988
87 349 829
338 350 197
83 351 309
336 352 383
185 353 441
181 354 74
225 355 590
256 356 247
110 357 859
50 358 365
219 359 642
224 360 72
64 361 595
203 362 921
306 363 930
203 364 298
120 365 547
293 366 11
61 367 836
76 368 196
142 369 686
332 370 618
294 371 948
239 372 278
291 373 667
234 374 337
351 375 560
50 376 124
198 377 585
54 378 319
230 379 891
69 380 400
42 381 981
153 382 902
14 383 475
297 384 200
120 385 465
107 386 26
336 387 895
9 388 841
297 389 583
118 390 987
261 391 499
119 392 923
243 393 311
299 394 85
368 395 790
190 396 694
260 397 853
109 398 533
35 399 6
198 400 891
164 401 134
151 402 720
367 403 241
239 404 687
248 405 316
369 406 72
278 407 504
209 408 380
389 409 623
199 410 64
10 411 351
209 412 857
91 413 790
62 414 841
254 415 423
298 416 956
127 417 111
365 418 628
322 419 111
312 420 662
251 421 923
2 422 561
44 423 936
245 424 775
424 425 821
324 426 360
49 427 904
366 428 90
120 429 916
28 430 31
62 431 801
107 432 563
151 433 287
72 434 428
359 435 315
29 436 727
80 437 680
423 438 180
103 439 631
376 440 715
428 441 628
46 442 356
293 443 981
30 444 16
225 445 594
180 446 55
250 447 392
316 448 526
153 449 489
424 450 623
71 451 544
143 452 527
155 453 558
221 454 689
224 455 280
264 456 926
180 457 6
23 458 803
133 459 48
159 460 649
95 461 617
199 462 943
215 463 574
211 464 419
291 465 936
127 466 182
368 467 313
219 468 974
182 469 176
337 470 397
420 471 613
299 472 832
151 473 255
467 474 108
190 475 661
448 476 148
236 477 318
184 478 16
112 479 174
311 480 579
306 481 344
283 482 69
369 483 312
3 484 339
107 485 697
238 486 233
125 487 346
429 488 663
401 489 378
437 490 342
340 491 415
232 492 104
422 493 596
210 494 39
361 495 547
271 496 124
36 497 402
295 498 837
214 499 898
202 500 412
202 501 916
61 502 355
274 503 802
135 504 667
250 505 897
84 506 271
106 507 544
454 508 325
429 509 53
281 510 43
510 511 216
200 512 461
89 513 523
387 514 468
159 515 849
358 516 842
403 517 276
142 518 274
34 519 232
425 520 291
309 521 464
32 522 816
403 523 203
254 524 713
108 525 836
15 526 173
68 527 425
111 528 900
437 529 485
229 530 362
178 531 296
129 532 946
209 533 219
383 534 565
206 535 799
1 536 709
233 537 289
379 538 647
7 539 532
67 540 187
216 541 861
7 542 906
497 543 176
177 544 450
369 545 795
270 546 70
386 547 690
414 548 148
280 549 606
320 550 628
416 551 49
270 552 344
18 553 849
469 554 131
344 555 510
114 556 139
282 557 778
345 558 249
228 559 753
80 560 246
404 561 368
382 562 261
117 563 290
413 564 495
483 565 126
476 566 429
256 567 458
230 568 541
104 569 952
451 570 410
173 571 883
150 572 639
304 573 822
307 574 563
398 575 885
559 576 325
46 577 703
536 578 241
342 579 546
113 580 330
137 581 719
427 582 143
555 583 469
83 584 105
462 585 108
549 586 797
261 587 302
43 588 846
416 589 157
353 590 61
116 591 785
83 592 87
396 593 931
445 594 278
433 595 447
140 596 324
399 597 85
339 598 153
236 599 45
138 600 451
11 601 326
453 602 481
77 603 563
508 604 120
394 605 985
83 606 335
270 607 23
278 608 411
475 609 464
446 610 62
249 611 651
446 612 683
339 613 777
229 614 530
563 615 284
302 616 187
411 617 362
325 618 399
447 619 237
366 620 171
57 621 342
317 622 696
439 623 819
195 624 553
57 625 39
138 626 117
416 627 345
593 628 263
294 629 462
188 630 442
367 631 766
387 632 480
302 633 866
529 634 532
5 635 774
30 636 886
541 637 318
465 638 702
309 639 390
335 640 390
483 641 589
60 642 868
367 643 556
45 644 887
294 645 929
619 646 942
262 647 630
76 648 712
335 649 426
386 650 105
177 651 681
62 652 25
381 653 268
373 654 345
51 655 573
385 656 371
7 657 796
223 658 346
417 659 407
519 660 706
303 661 604
366 662 623
588 663 191
32 664 674
285 665 901
156 666 35
136 667 739
579 668 34
366 669 764
79 670 744
541 671 306
507 672 773
658 673 319
401 674 693
435 675 405
457 676 927
357 677 505
371 678 356
536 679 507
101 680 879
421 681 693
307 682 922
447 683 212
41 684 792
597 685 400
653 686 57
531 687 657
259 688 797
2 689 745
172 690 916
323 691 321
415 692 445
243 693 677
194 694 426
409 695 391
608 696 796
356 697 174
565 698 566
439 699 481
576 700 939
548 701 747
218 702 276
203 703 332
348 704 409
181 705 958
284 706 823
694 707 942
56 708 378
204 709 225
448 710 49
373 711 820
93 712 568
264 713 658
76 714 852
189 715 237
600 716 920
389 717 401
540 718 856
303 719 870
522 720 416
566 721 15
453 722 900
594 723 879
321 724 462
33 725 802
271 726 17
570 727 701
231 728 731
159 729 285
303 730 476
371 731 666
661 732 329
508 733 125
118 734 739
110 735 18
26 736 329
342 737 841
714 738 651
140 739 679
21 740 872
344 741 681
374 742 320
218 743 183
288 744 796
438 745 746
239 746 301
74 747 772
692 748 634
144 749 24
746 750 318
189 751 243
730 752 915
624 753 462
310 754 826
648 755 641
538 756 983
238 757 250
251 758 357
528 759 379
46 760 57
490 761 500
474 762 230
543 763 749
266 764 324
25 765 231
208 766 246
582 767 501
313 768 413
258 769 425
65 770 521
629 771 512
47 772 298
261 773 272
258 774 336
761 775 709
269 776 66
754 777 693
461 778 206
449 779 329
735 780 942
466 781 805
401 782 882
399 783 362
717 784 46
154 785 53
643 786 878
223 787 544
603 788 48
617 789 269
414 790 278
408 791 576
758 792 125
538 793 209
668 794 644
2 795 594
7 796 917
736 797 348
198 798 546
565 799 806
782 800 437
453 801 909
718 802 793
32 803 354
148 804 143
598 805 750
99 806 192
519 807 655
579 808 98
384 809 378
59 810 191
445 811 388
139 812 658
512 813 927
4 814 445
289 815 546
441 816 130
401 817 108
478 818 256
8 819 762
710 820 79
703 821 445
665 822 788
100 823 268
822 824 744
529 825 644
415 826 62
698 827 641
204 828 755
172 829 586
86 830 682
84 831 379
220 832 314
43 833 902
77 834 706
684 835 155
375 836 831
475 837 708
73 838 297
139 839 475
573 840 445
475 841 386
205 842 640
759 843 781
791 844 592
474 845 391
469 846 408
641 847 563
304 848 494
369 849 356
756 850 263
348 851 976
123 852 22
728 853 360
269 854 639
353 855 847
3 856 120
244 857 758
809 858 420
199 859 362
684 860 279
178 861 409
537 862 517
778 863 110
123 864 11
96 865 899
573 866 822
512 867 628
669 868 643
434 869 954
132 870 411
559 871 131
544 872 946
385 873 980
198 874 185
266 875 420
313 876 319
175 877 292
607 878 585
850 879 709
850 880 554
70 881 381
838 882 692
325 883 698
207 884 356
227 885 878
133 886 102
2 887 89
407 888 199
184 889 647
812 890 373
673 891 69
232 892 376
514 893 866
76 894 506
827 895 389
640 896 993
400 897 429
318 898 243
629 899 830
453 900 842
448 901 919
685 902 262
894 903 461
900 904 97
565 905 761
470 906 785
538 907 97
157 908 952
644 909 807
690 910 640
497 911 752
134 912 431
284 913 342
341 914 696
587 915 777
41 916 346
848 917 192
353 918 386
603 919 898
771 920 357
135 921 534
165 922 138
657 923 962
539 924 46
199 925 861
515 926 594
636 927 578
197 928 682
168 929 292
814 930 122
852 931 527
315 932 852
904 933 884
165 934 282
193 935 59
357 936 282
539 937 32
574 938 33
657 939 252
777 940 617
388 941 959
382 942 815
829 943 749
94 944 571
816 945 8
151 946 208
588 947 579
923 948 879
868 949 22
232 950 587
388 951 202
12 952 121
479 953 891
646 954 908
422 955 730
169 956 865
477 957 281
114 958 501
330 959 468
137 960 480
850 961 911
782 962 594
477 963 657
724 964 417
823 965 320
733 966 574
192 967 156
459 968 582
871 969 442
242 970 585
869 971 358
444 972 60
208 973 93
577 974 588
800 975 818
646 976 889
780 977 10
833 978 23
105 979 178
53 980 651
839 981 311
964 982 257
298 983 226
665 984 699
834 985 648
156 986 976
73 987 915
756 988 458
505 989 231
960 990 595
267 991 378
46 992 315
475 993 166
590 994 837
548 995 226
526 996 754
672 997 292
96 998 740
599 999 271
272 1000 908
597 683 244
23
620 560 383 467 342 217 720 133 893 322 914 126 529 314 117 80 326 494 780 270 254 463 492
1000
641 847
103 303
139 812
151 203
17 65
559 871
508 604
56 13
60 195
114 46
272 1000
155 67
43 588
67 540
202 6
718 802
186 241
475 993
510 281
30 444
74 240
849 369
7 51
228 180
371 731
611 249
481 306
610 446
191 333
747 74
721 566
532 129
145 67
741 344
105 979
73 148
354 181
192 967
415 826
96 85
38 20
453 602
706 284
866 573
57 625
33 151
218 702
389 717
454 508
348 851
249 27
32 803
83 592
809 858
486 238
238 757
14 61
243 211
35 270
854 269
936 357
135 504
261 773
890 812
159 338
47 178
685 902
964 982
232 492
2 422
173 113
380 69
543 497
275 157
540 718
316 16
177 209
96 121
443 293
524 254
437 80
342 737
271 61
427 49
815 289
229 223
36 497
292 157
930 814
513 89
101 112
319 272
28 101
874 198
304 848
614 229
60 642
565 698
177 544
421 681
100 154
74 98
962 782
165 164
235 132
53 17
274 120
684 860
907 538
341 914
459 133
169 142
965 823
448 476
875 266
103 159
401 817
601 11
343 297
200 512
274 285
905 565
345 558
51 655
712 93
193 935
3 57
208 973
82 30
291 345
342 579
352 336
366 620
600 716
579 668
560 80
430 28
562 382
461 778
332 218
518 142
48 67
564 413
392 119
477 957
520 425
672 997
563 615
756 988
188 101
297 239
141 311
682 307
61 367
298 223
237 288
337 470
898 318
4 5
768 313
549 586
894 76
62 289
303 719
110 74
395 368
365 120
194 694
449 153
199 462
184 478
871 969
53 980
15 102
263 157
144 277
637 541
68 210
123 28
122 16
733 966
212 143
14 383
665 984
237 42
446 180
607 270
783 399
498 295
589 416
521 309
820 710
833 43
441 428
453 155
497 911
123 864
189 751
10 26
735 110
646 976
314 112
103 45
81 57
49 2
202 329
59 221
97 299
408 791
378 54
326 263
121 201
74 216
645 294
75 167
674 401
204 125
199 410
116 97
304 150
124 189
587 915
176 184
879 850
182 469
153 382
700 576
736 26
400 897
59 810
194 301
118 390
5 28
886 133
823 100
632 387
73 838
653 381
21 75
838 882
474 762
825 529
142 369
4 814
738 714
590 994
193 127
44 86
261 587
710 448
943 829
9 388
606 83
388 951
679 536
130 226
144 194
856 3
437 529
830 86
4 1
373 711
386 547
441 816
251 758
107 432
5 219
298 416
917 848
16 12
61 302
3 8
406 369
94 61
624 195
181 83
320 267
239 50
912 134
399 597
424 425
183 61
452 143
154 785
538 379
15 135
125 487
209 250
10 187
258 769
508 733
164 269
569 104
340 491
485 107
66 258
777 940
87 251
771 920
805 598
755 648
5 130
156 291
69 341
330 959
276 163
266 764
270 546
853 728
595 433
833 978
147 190
57 621
931 852
509 429
913 284
767 582
365 418
800 975
618 325
21 12
92 26
3 2
79 104
335 640
445 811
526 996
80 225
827 698
507 106
72 20
64 43
208 178
585 462
322 108
445 225
503 274
933 904
311 480
84 506
6 87
375 351
861 178
156 666
173 571
202 501
151 402
932 315
18 24
792 758
469 846
723 594
819 8
51 129
83 34
684 41
759 843
574 938
214 254
367 631
223 252
348 704
593 396
342 204
514 387
850 961
778 863
39 25
204 709
923 948
99 46
730 303
213 184
507 672
203 364
539 924
228 559
32 664
278 407
14 80
55 93
128 160
536 578
219 359
205 48
258 317
7 542
227 153
779 449
777 754
999 599
310 754
12 2
111 528
2 1
244 321
658 673
626 138
439 103
472 299
804 148
84 126
73 207
288 744
17 15
176 280
919 603
97 24
670 79
447 619
65 134
171 34
683 597
736 797
889 184
232 950
515 159
278 109
294 629
207 884
900 453
947 588
171 257
357 110
60 334
54 1
356 697
24 45
115 124
671 541
313 120
222 233
57 66
743 218
127 147
742 374
946 151
48 23
10 411
233 537
348 169
124 140
929 168
727 570
177 651
267 991
45 158
573 304
500 202
83 351
114 556
644 45
4 25
29 10
842 205
415 692
774 258
180 143
154 337
102 246
714 76
790 414
236 34
476 566
388 941
290 188
164 103
42 38
971 869
175 877
596 140
763 543
303 661
1 234
359 435
7 796
353 185
448 316
577 46
137 65
51 128
545 369
528 759
372 239
467 368
73 186
38 50
577 974
281 9
47 772
668 794
538 756
813 512
152 24
800 782
619 646
605 394
944 94
62 44
35 12
78 191
624 753
466 127
339 613
512 867
458 23
423 44
217 16
108 525
895 827
116 591
130 339
33 725
366 428
385 656
887 2
170 32
477 236
701 548
489 401
198 798
89 69
339 598
357 677
101 680
242 34
234 374
636 927
17 90
306 363
839 981
68 527
522 720
143 15
19 8
985 834
654 373
622 317
168 9
221 454
475 609
570 451
46 70
952 12
202 310
937 539
294 264
99 806
18 6
756 850
197 51
536 1
708 56
108 27
113 328
144 340
473 151
3 484
401 782
633 302
539 7
210 494
488 429
643 367
474 467
136 667
77 603
424 245
862 537
555 344
629 899
26 218
285 665
608 696
516 358
435 675
265 218
561 404
297 389
225 355
923 657
346 201
208 766
409 389
972 444
206 535
199 859
336 387
146 66
431 62
239 404
475 841
196 88
788 603
398 575
381 42
623 439
353 918
9 8
873 385
166 104
23 9
22 136
137 266
15 4
330 142
688 259
572 150
127 172
358 50
46 21
127 71
904 900
30 10
91 220
47 42
4 247
816 945
84 831
748 692
519 34
239 746
217 283
617 411
641 483
307 64
901 448
61 502
722 453
134 306
382 942
149 15
109 398
463 215
760 46
469 554
690 172
144 749
248 25
608 278
593 628
505 989
369 483
729 159
844 791
649 335
122 244
58 60
164 401
52 192
3 11
580 113
949 868
230 379
557 282
156 86
466 781
648 76
635 5
1 22
136 230
30 636
438 423
118 734
652 62
970 242
517 403
297 384
23 142
2 336
200 156
269 776
475 190
286 79
822 824
793 538
629 771
493 422
2 795
750 746
107 33
115 106
78 161
36 214
327 301
916 41
958 114
752 730
375 836
840 573
20 74
590 353
33 315
307 574
203 703
58 50
464 211
138 600
653 686
551 416
770 65
567 256
150 25
446 612
238 192
821 703
262 22
883 325
669 868
955 422
822 665
175 16
91 19
872 544
7 13
55 138
479 953
185 13
332 370
892 232
53 199
14 71
412 209
9 109
745 438
960 137
272 213
922 165
865 96
660 519
478 818
514 893
691 323
320 550
420 471
475 837
283 482
658 223
403 367
85 113
188 215
885 227
46 442
460 159
300 35
616 302
644 909
393 243
360 224
123 198
177 78
35 40
373 291
261 163
910 690
9 14
57 88
287 125
447 250
400 198
968 459
650 386
100 324
350 338
926 515
210 344
44 18
784 717
331 188
735 780
131 111
37 18
208 253
268 64
888 407
657 939
6 5
523 403
801 453
832 220
324 426
64 361
157 102
123 852
33 6
55 40
775 761
891 673
68 31
59 7
440 376
607 878
24 52
282 31
7 6
377 198
114 295
105 6
684 835
510 511
413 91
559 576
11 34
335 195
415 254
599 236
699 439
160 293
49 245
707 694
41 22
18 553
273 347
264 456
127 144
436 29
663 588
445 594
8 264
457 676
62 414
118 20
385 120
120 429
223 787
162 46
101 318
483 565
197 928
85 32
960 990
84 82
881 70
903 894
78 296
8 231
27 2
206 157
98 120
255 80
534 383
229 530
157 908
522 32
880 850
361 495
568 230
35 399
761 490
541 216
83 584
209 533
9 10
139 24
461 95
174 160
31 17
179 89
199 925
133 78
465 291
248 405
857 244
132 38
630 188
906 470
366 662
427 582
705 181
397 260
807 519
356 256
165 934
839 139
992 46
548 414
552 270
638 465
185 256
37 78
10 69
457 180
250 505
71 451
687 531
135 921
447 683
69 325
479 112
529 634
95 69
51 117
419 322
437 490
640 896
829 172
96 998
260 239
581 137
111 50
2 689
15 526
17 20
724 321
284 64
349 87
450 424
693 243
49 309
855 353
57 79
323 78
50 376
366 293
739 140
954 646
76 368
233 267
10 211
31 43
169 956
808 579
271 726
695 409
259 53
496 271
129 163
77 141
474 845
65 100
184 312
531 178
713 264
657 7
55 76
715 189
151 433
987 73
232 226
224 455
834 77
32 12
964 724
799 565
305 42
261 391
209 408
119 38
117 563
371 294
617 789
420 312
176 109
384 809
434 869
78 153
17 63
44 224
583 555
685 597
132 870
128 308
732 661
25 765
21 77
203 362
647 262
468 219
106 26
25 36
396 190
231 728
548 995
669 366
780 977
127 417
477 963
309 639
627 416
299 394
786 643
97 279
499 214
434 72
983 298
876 313
273 227
204 828
549 280
417 659
159 182
107 386
371 678
141 222
9 73
251 421
21 740
98 125
107 223
986 156