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