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