1 1 2 2 3 4 4 3 5 6 6 7 7 9 8 5 9 8 10 13 11 12 12 17 13 14 14 23 15 16 16 11 17 10 18 19 19 15 20 41 21 22 22 37 23 21 24 59 25 27 26 43 27 24 28 83 29 35 30 53 31 26 32 31 33 20 34 29 35 18 36 67 37 30 38 47 39 25 40 179 41 58 42 79 43 34 44 157 45 54 46 73 47 33 48 277 49 82 50 103 51 40 52 191 53 62 54 89 55 36 56 431 57 114 58 149 59 51 60 241 61 75 62 101 63 39 64 127 65 46 66 71 67 32 68 109 69 44 70 61 71 28 72 331 73 92 74 113 75 45 76 211 77 66 78 97 79 38 80 1063 81 230 82 271 83 81 84 401 85 108 86 139 87 50 88 919 89 204 90 251 91 76 92 367 93 99 94 137 95 49 96 1787 97 346 98 421 99 112 100 563 101 136 102 173 103 57 104 1153 105 245 106 293 107 86 108 461 109 120 110 151 111 52 112 3001 113 531 114 619 115 150 116 859 117 194 118 233 119 72 120 1523 121 304 122 379 123 102 124 547 125 134 126 167 127 56 128 709 129 166 130 199 131 65 132 353 133 96 134 131 135 48 136 599 137 144 138 193 139 63 140 283 141 85 142 107 143 42 144 2221 145 412 146 479 147 123 148 617 149 148 150 197 151 64 152 1297 153 268 154 317 155 91 156 509 157 129 158 163 159 55 160 8527 161 1269 162 1451 163 292 164 1741 165 340 166 419 167 111 168 2749 169 496 170 593 171 143 172 797 173 182 174 229 175 70 176 7193 177 1105 178 1249 179 260 180 1597 181 318 182 383 183 104 184 2477 185 455 186 523 187 132 188 773 189 178 190 227 191 69 192 15299 193 2105 194 2339 195 429 196 2909 197 519 198 613 199 147 200 4091 201 688 202 769 203 177 204 1031 205 221 206 269 207 80 208 9319 209 1374 210 1553 211 309 212 1913 213 366 214 443 215 117 216 3259 217 565 218 659 219 158 220 877 221 196 222 239 223 74 224 27457 225 3489 226 3823 227 650 228 4567 229 753 230 863 231 195 232 6661 233 1034 234 1181 235 248 236 1471 237 296 238 359 239 98 240 12763 241 1803 242 2003 243 380 244 2609 245 471 246 557 247 135 248 3943 249 669 250 757 251 175 252 991 253 215 254 263 255 78 256 5381 257 858 258 983 259 214 260 1217 261 254 262 313 263 90 264 2381 265 438 266 503 267 128 268 739 269 171 270 223 271 68 272 4397 273 729 274 827 275 187 276 1171 277 247 278 307 279 87 280 1847 281 355 282 439 283 116 284 587 285 142 286 181 287 60 288 19577 289 2600 290 2837 291 510 292 3407 293 586 294 677 295 161 296 4549 297 750 298 857 299 192 300 1201 301 252 302 311 303 88 304 10631 305 1540 306 1721 307 336 308 2099 309 395 310 467 311 122 312 3637 313 624 314 727 315 169 316 967 317 210 318 257 319 77 320 87803 321 9727 322 10337 323 1509 324 12113 325 1719 326 1907 327 365 328 14867 329 2051 330 2287 331 423 332 2897 333 517 334 607 335 146 336 24859 337 3202 338 3541 339 608 340 4339 341 722 342 823 343 186 344 6113 345 960 346 1091 347 234 348 1447 349 291 350 349 351 95 352 72727 353 8225 354 8863 355 1322 356 10169 357 1485 358 1657 359 327 360 13469 361 1887 362 2111 363 396 364 2647 365 475 366 569 367 138 368 22093 369 2896 370 3217 371 558 372 3761 373 639 374 743 375 172 376 5869 377 932 378 1061 379 228 380 1433 381 289 382 347 383 94 384 167449 385 17286 386 18371 387 2471 388 20759 389 2739 390 2971 391 529 392 26489 393 3386 394 3719 395 635 396 4517 397 746 398 853 399 190 400 38833 401 4730 402 5167 403 834 404 5851 405 927 406 1051 407 226 408 8221 409 1234 410 1381 411 282 412 1723 413 338 414 409 415 110 416 96797 417 10615 418 11383 419 1633 420 13037 421 1836 422 2039 423 386 424 16519 425 2248 426 2473 427 454 428 3109 429 544 430 643 431 154 432 30133 433 3786 434 4099 435 690 436 4933 437 799 438 929 439 205 440 6823 441 1055 442 1193 443 250 444 1499 445 302 446 373 447 100 448 318211 449 30776 450 32507 451 4047 452 35993 453 4426 454 4831 455 789 456 43889 457 5266 458 5717 459 909 460 6691 461 1038 462 1187 463 249 464 66851 465 7630 466 8237 467 1238 468 9539 469 1404 470 1571 471 314 472 12301 473 1743 474 1949 475 370 476 2417 477 446 478 521 479 130 480 137077 481 14459 482 15439 483 2123 484 17417 485 2353 486 2617 487 472 488 23431 489 3046 490 3343 491 578 492 4027 493 681 494 761 495 176 496 37217 497 4562 498 4999 499 810 500 5749 501 914 502 1039 503 224 504 7841 505 1186 506 1319 507 274 508 1669 509 330 510 397 511 106 512 52711 513 6186 514 6659 515 1032 516 7753 517 1177 518 1307 519 273 520 9859 521 1446 522 1609 523 321 524 2081 525 391 526 463 527 121 528 21179 529 2786 530 3061 531 538 532 3593 533 616 534 719 535 168 536 5623 537 894 538 1019 539 219 540 1409 541 285 542 337 543 93 544 42043 545 5075 546 5519 547 882 548 6353 549 995 550 1117 551 240 552 9461 553 1393 554 1567 555 312 556 2027 557 384 558 449 559 118 560 15823 561 2174 562 2389 563 441 564 3067 565 539 566 641 567 153 568 4273 569 715 570 821 571 185 572 1087 573 232 574 281 575 84 576 219613 577 22048 578 23321 579 3035 580 25763 581 3302 582 3643 583 625 584 31667 585 3956 586 4271 587 714 588 5059 589 819 590 947 591 208 592 43651 593 5247 594 5693 595 905 596 6653 597 1030 598 1163 599 246 600 9739 601 1426 602 1601 603 319 604 2063 605 388 606 457 607 119 608 112129 609 12078 610 12923 611 1821 612 14713 613 2030 614 2267 615 417 616 18311 617 2464 618 2711 619 489 620 3319 621 573 622 673 623 160 624 33967 625 4214 626 4621 627 759 628 5503 629 879 630 1009 631 217 632 7607 633 1159 634 1291 635 267 636 1621 637 324 638 389 639 105 640 1128889 641 97150 642 101561 643 11068 644 108739 645 11747 646 12637 647 1786 648 129443 649 13739 650 14683 651 2026 652 16451 653 2241 654 2467 655 453 656 162257 657 16807 658 17903 659 2409 660 20231 661 2675 662 2927 663 522 664 26371 665 3374 666 3701 667 633 668 4463 669 738 670 839 671 189 672 285191 673 27905 674 29473 675 3722 676 33029 677 4107 678 4481 679 740 680 41491 681 5012 682 5471 683 873 684 6323 685 990 686 1109 687 238 688 60647 689 7016 690 7561 691 1150 692 8747 693 1305 694 1481 695 297 696 12097 697 1715 698 1901 699 364 700 2351 701 434 702 499 703 126 704 919913 705 80615 706 84391 707 9386 708 91711 709 10105 710 10867 711 1570 712 106699 713 11562 714 12437 715 1760 716 14051 717 1955 718 2179 719 407 720 145547 721 15249 722 16231 723 2218 724 18433 725 2479 726 2713 727 490 728 23801 729 3090 730 3371 731 582 732 4133 733 695 734 787 735 180 736 250751 737 24839 738 26357 739 3372 740 29641 741 3740 742 4049 743 682 744 35311 745 4356 746 4733 747 777 748 5651 749 898 750 1021 751 220 752 57943 753 6739 754 7309 755 1120 756 8513 757 1267 758 1439 759 290 760 11953 761 1700 762 1879 763 362 764 2341 765 430 766 491 767 125 768 2269733 769 184124 770 191509 771 19499 772 204859 773 20702 774 22051 775 2890 776 234167 777 23364 778 24763 779 3192 780 27091 781 3454 782 3803 783 648 784 305999 785 29711 786 31469 787 3933 788 34843 789 4310 790 4703 791 772 792 43283 793 5211 794 5659 795 901 796 6599 797 1026 798 1151 799 244 800 464939 801 43356 802 45641 803 5452 804 50341 805 5948 806 6397 807 1003 808 57751 809 6718 810 7247 811 1114 812 8389 813 1256 814 1429 815 288 816 84347 817 9382 818 10061 819 1467 820 11447 821 1641 822 1831 823 354 824 14723 825 2032 826 2273 827 420 828 2803 829 506 830 601 831 145 832 1254739 833 106996 834 111949 835 12060 836 120929 837 12924 838 13807 839 1927 840 140339 841 14768 842 15739 843 2163 844 17761 845 2396 846 2663 847 478 848 182261 849 18650 850 19867 851 2630 852 22067 853 2892 854 3209 855 556 856 28573 857 3615 858 3923 859 666 860 4787 861 781 862 887 863 201 864 352007 865 33746 866 35543 867 4384 868 38917 869 4739 870 5179 871 836 872 47857 873 5681 874 6131 875 962 876 7283 877 1116 878 1259 879 261 880 68639 881 7811 882 8431 883 1261 884 9661 885 1417 886 1583 887 316 888 12547 889 1774 890 1997 891 377 892 2549 893 464 894 541 895 133 896 4535189 897 348034 898 360257 899 34456 900 382801 901 36366 902 38329 903 4681 904 427919 905 40218 906 42337 907 5110 908 46751 909 5566 910 6047 911 951 912 530773 913 48920 914 51461 915 6057 916 56393 917 6566 918 7079 919 1092 920 67157 921 7663 922 8273 923 1242 924 9619 925 1411 926 1579 927 315 928 839483 929 74169 930 77641 931 8717 932 84499 933 9400 934 10091 935 1472 936 99391 937 10860 938 11699 939 1666 940 13217 941 1855 942 2083 943 392 944 131707 945 13950 946 14879 947 2054 948 16901 949 2290 950 2531 951 459 952 21529 953 2828 954 3137 955 548 956 3733 957 637 958 733 959 170 960 1828669 961 151014 962 157247 963 16356 964 169321 965 17446 966 18539 967 2491 968 193009 969 19643 970 20921 971 2756 972 23539 973 3055 974 3347 975 579 976 267439 977 26325 978 27917 979 3543 980 31033 981 3882 982 4219 983 705 984 38153 985 4658 986 5099 987 825 988 5801 989 918 990 1049 991 225 992 443419 993 41564 994 43789 995 5260 996 48593 997 5757 998 6221 999 975 1000 56701