1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 3 9 7 10 13 11 25 12 3 13 19 14 6 15 35 16 19 17 2 18 19 19 21 20 59 21 62 22 54 23 10 24 62 25 18 26 12 27 23 28 80 29 96 30 67 31 111 32 96 33 5 34 78 35 132 36 8 37 128 38 98 39 123 40 143 41 12 42 141 43 40 44 98 45 90 46 88 47 53 48 93 49 97 50 187 51 186 52 47 53 2 54 117 55 241 56 34 57 27 58 51 59 266 60 108 61 259 62 115 63 278 64 30 65 281 66 227 67 244 68 141 69 24 70 131 71 187 72 244 73 271 74 262 75 84 76 192 77 163 78 241 79 115 80 78 81 316 82 187 83 250 84 327 85 155 86 13 87 232 88 297 89 14 90 13 91 264 92 274 93 351 94 344 95 141 96 347 97 180 98 88 99 150 100 419 101 238 102 272 103 54 104 14 105 360 106 106 107 237 108 294 109 391 110 491 111 75 112 49 113 540 114 191 115 180 116 37 117 595 118 301 119 364 120 329 121 469 122 211 123 174 124 39 125 224 126 103 127 664 128 489 129 686 130 617 131 299 132 240 133 550 134 40 135 602 136 333 137 173 138 738 139 679 140 575 141 288 142 329 143 619 144 335 145 292 146 439 147 205 148 856 149 426 150 212 151 627 152 178 153 844 154 782 155 792 156 143 157 89 158 697 159 13 160 134 161 526 162 214 163 771 164 745 165 693 166 605 167 927 168 969 169 404 170 85 171 70 172 889 173 852 174 950 175 288 176 749 177 747 178 611 179 1032 180 318 181 308 182 395 183 124 184 944 185 951 186 299 187 810 188 148 189 970 190 897 191 925 192 440 193 1118 194 749 195 399 196 1099 197 856 198 191 199 624 200 934 201 900 202 969 203 830 204 1169 205 968 206 187 207 599 208 129 209 647 210 967 211 1110 212 1147 213 360 214 28 215 69 216 1034 217 199 218 104 219 153 220 662 221 333 222 55 223 321 224 1420 225 765 226 140 227 1150 228 414 229 1423 230 195 231 175 232 94 233 979 234 217 235 537 236 518 237 1102 238 986 239 540 240 1042 241 286 242 823 243 817 244 1466 245 275 246 1262 247 11 248 1398 249 1015 250 787 251 323 252 831 253 213 254 815 255 1337 256 1100 257 1147 258 369 259 30 260 620 261 777 262 1140 263 569 264 1222 265 87 266 834 267 1052 268 59 269 534 270 1541 271 979 272 1462 273 950 274 388 275 948 276 1021 277 457 278 93 279 1137 280 1369 281 872 282 416 283 350 284 1641 285 622 286 1856 287 142 288 663 289 1678 290 1472 291 1837 292 1241 293 1128 294 926 295 1371 296 1885 297 203 298 1544 299 339 300 1669 301 660 302 1460 303 692 304 574 305 584 306 112 307 1369 308 353 309 782 310 1889 311 301 312 1487 313 1498 314 2073 315 1930 316 831 317 1976 318 834 319 1334 320 1639 321 361 322 527 323 787 324 772 325 2030 326 266 327 1725 328 1198 329 705 330 621 331 584 332 1310 333 1867 334 156 335 319 336 432 337 305 338 1067 339 1982 340 710 341 477 342 2239 343 1495 344 343 345 1676 346 809 347 820 348 360 349 437 350 182 351 452 352 1319 353 1431 354 689 355 1911 356 2175 357 1544 358 1061 359 939 360 1779 361 755 362 1395 363 1509 364 1467 365 408 366 240 367 107 368 2029 369 1870 370 1948 371 1072 372 1932 373 1240 374 1286 375 2330 376 656 377 1319 378 1395 379 402 380 1539 381 767 382 1102 383 1276 384 2210 385 1803 386 2575 387 1516 388 1943 389 2583 390 333 391 2411 392 1005 393 933 394 2500 395 1081 396 2465 397 452 398 2550 399 1945 400 537 401 1448 402 2691 403 2139 404 1459 405 1294 406 1899 407 1859 408 279 409 2719 410 1089 411 2138 412 603 413 2641 414 2520 415 1128 416 2147 417 1821 418 90 419 2001 420 803 421 1081 422 2713 423 2898 424 2276 425 488 426 2882 427 2648 428 1907 429 685 430 2362 431 174 432 298 433 2082 434 2087 435 2739 436 1659 437 502 438 1679 439 22 440 2001 441 1366 442 1797 443 924 444 908 445 1904 446 719 447 384 448 2241 449 638 450 851 451 1627 452 1328 453 2069 454 1079 455 2234 456 3027 457 671 458 1399 459 862 460 1502 461 1426 462 1086 463 3064 464 58 465 3089 466 581 467 208 468 407 469 1429 470 2825 471 33 472 870 473 1159 474 2058 475 2757 476 2812 477 440 478 2803 479 101 480 1115 481 2083 482 2497 483 961 484 183 485 1802 486 2899 487 2232 488 2989 489 2825 490 279 491 1472 492 604 493 561 494 2380 495 825 496 2161 497 2838 498 2226 499 2964 500 2315 501 139 502 815 503 1772 504 1987 505 670 506 480 507 1479 508 2354 509 67 510 2018 511 3536 512 1864 513 1109 514 2145 515 2359 516 498 517 2576 518 1406 519 849 520 2644 521 1008 522 1054 523 1871 524 3593 525 2413 526 3059 527 672 528 677 529 1977 530 680 531 1695 532 1312 533 2533 534 2809 535 27 536 2243 537 3006 538 2421 539 3440 540 1492 541 1708 542 3169 543 2139 544 392 545 1606 546 306 547 935 548 992 549 1519 550 752 551 2111 552 163 553 1493 554 420 555 1979 556 3083 557 3654 558 2262 559 3196 560 976 561 455 562 2928 563 3678 564 2721 565 8 566 3142 567 2522 568 2184 569 3502 570 1221 571 3520 572 2436 573 880 574 1315 575 1941 576 3523 577 3483 578 905 579 4203 580 1710 581 758 582 339 583 980 584 518 585 2711 586 3260 587 1563 588 3288 589 2056 590 3156 591 1218 592 2517 593 2284 594 1880 595 33 596 1951 597 4093 598 3515 599 2294 600 1168 601 1926 602 352 603 1363 604 1300 605 1279 606 4206 607 3904 608 625 609 1538 610 3393 611 4196 612 2761 613 1173 614 2037 615 1994 616 1986 617 3387 618 3991 619 1186 620 2300 621 2067 622 4373 623 4410 624 4292 625 3163 626 861 627 2721 628 3830 629 2898 630 2353 631 2310 632 4660 633 66 634 1213 635 1 636 1088 637 1291 638 1597 639 3372 640 1300 641 4668 642 3815 643 1096 644 4504 645 4353 646 4169 647 1469 648 3263 649 2927 650 3974 651 118 652 2674 653 3172 654 3987 655 1638 656 3147 657 4891 658 1118 659 1319 660 463 661 3021 662 1203 663 3040 664 1224 665 4312 666 2993 667 1157 668 879 669 3672 670 1936 671 4108 672 2569 673 852 674 2286 675 1944 676 3497 677 4198 678 3783 679 4754 680 3232 681 4992 682 1120 683 4816 684 1680 685 3561 686 1674 687 1573 688 605 689 2060 690 1694 691 1067 692 1330 693 3807 694 4514 695 1616 696 1017 697 1747 698 5056 699 2748 700 3925 701 413 702 4691 703 4402 704 4076 705 5082 706 4978 707 3520 708 560 709 2321 710 3153 711 4417 712 3023 713 840 714 2049 715 3051 716 3243 717 3795 718 3326 719 447 720 3632 721 1454 722 1575 723 433 724 4079 725 3096 726 3455 727 2734 728 1014 729 3698 730 3622 731 2056 732 954 733 2665 734 1700 735 5216 736 5532 737 108 738 437 739 4160 740 4312 741 2534 742 1831 743 2138 744 5367 745 1092 746 4989 747 4405 748 329 749 2032 750 1711 751 2898 752 725 753 4810 754 1374 755 4652 756 1368 757 5298 758 1034 759 3425 760 576 761 5456 762 5477 763 4349 764 3191 765 3068 766 5653 767 3739 768 5192 769 1519 770 3924 771 3088 772 2780 773 4335 774 5190 775 664 776 4705 777 4146 778 689 779 5120 780 5915 781 930 782 3564 783 4481 784 4933 785 5060 786 5727 787 1549 788 4970 789 2715 790 699 791 5526 792 3036 793 4612 794 2759 795 2974 796 12 797 2155 798 4569 799 4941 800 3181 801 3106 802 4077 803 1817 804 5238 805 3096 806 2055 807 940 808 1686 809 2921 810 4661 811 3739 812 5971 813 4861 814 361 815 1973 816 2659 817 3510 818 4386 819 180 820 1290 821 1639 822 5188 823 5066 824 6289 825 1955 826 130 827 1677 828 1939 829 5705 830 486 831 2292 832 4716 833 3178 834 842 835 2937 836 3905 837 187 838 1949 839 5115 840 1783 841 531 842 2450 843 1011 844 4805 845 988 846 4921 847 2590 848 1792 849 802 850 6343 851 4376 852 5878 853 1651 854 3750 855 5729 856 311 857 2026 858 2242 859 2857 860 4585 861 3108 862 2626 863 3399 864 1648 865 4767 866 978 867 3232 868 2571 869 814 870 1375 871 444 872 2386 873 6705 874 2934 875 5620 876 2375 877 1143 878 905 879 3800 880 2498 881 2739 882 828 883 723 884 6259 885 4782 886 1951 887 325 888 2967 889 3928 890 1186 891 5790 892 4560 893 3467 894 5157 895 6321 896 4829 897 6702 898 3100 899 600 900 4704 901 6262 902 1536 903 5373 904 792 905 4027 906 4745 907 5910 908 4350 909 2842 910 2341 911 4716 912 647 913 3471 914 2879 915 7089 916 3783 917 4170 918 2537 919 1504 920 5737 921 3484 922 4955 923 7056 924 2186 925 1314 926 1083 927 4990 928 3708 929 1489 930 151 931 6608 932 1231 933 7083 934 3583 935 4306 936 797 937 5601 938 5692 939 6371 940 3366 941 2050 942 847 943 2392 944 2564 945 6284 946 5126 947 168 948 1516 949 3071 950 5558 951 2831 952 3031 953 3395 954 5545 955 1471 956 6979 957 4340 958 6041 959 4178 960 1615 961 3517 962 4415 963 5338 964 5517 965 3574 966 467 967 4186 968 376 969 4744 970 6630 971 5949 972 1391 973 3174 974 1134 975 1936 976 1003 977 5462 978 3424 979 4356 980 5467 981 4853 982 6033 983 3772 984 1494 985 2361 986 1015 987 2060 988 6326 989 1073 990 1944 991 1280 992 4994 993 1865 994 3267 995 2475 996 3042 997 3112 998 6266 999 1641 1000 3345