1 1 2 4 3 7 4 13 5 13 6 25 7 19 8 38 9 37 10 49 11 31 12 74 13 37 14 73 15 79 16 104 17 49 18 125 19 55 20 143 21 121 22 121 23 67 24 203 25 121 26 145 27 171 28 221 29 85 30 263 31 91 32 272 33 205 34 193 35 199 36 354 37 109 38 217 39 247 40 383 41 121 42 398 43 127 44 377 45 381 46 265 47 139 48 531 49 253 50 443 51 331 52 455 53 157 54 558 55 355 56 587 57 373 58 337 59 175 60 720 61 181 62 361 63 567 64 688 65 433 66 698 67 199 68 611 69 457 70 725 71 211 72 927 73 217 74 433 75 687 76 689 77 481 78 848 79 235 80 985 81 729 82 481 83 247 84 1098 85 589 86 505 87 583 88 1022 89 265 90 1185 91 595 92 845 93 625 94 553 95 667 96 1342 97 289 98 953 99 951 100 1234 101 301 102 1148 103 307 104 1250 105 1149 106 625 107 319 108 1539 109 325 110 1250 111 751 112 1489 113 337 114 1298 115 823 116 1079 117 1173 118 697 119 823 120 1858 121 661 122 721 123 835 124 1157 125 965 126 1764 127 379 128 1696 129 877 130 1544 131 391 132 1914 133 937 134 793 135 1659 136 1706 137 409 138 1598 139 415 140 2032 141 961 142 841 143 847 144 2335 145 1057 146 865 147 1539 148 1391 149 445 150 2222 151 451 152 1934 153 1617 154 1781 155 1135 156 2325 157 469 158 937 159 1087 160 2458 161 1165 162 2322 163 487 164 1547 165 2001 166 985 167 499 168 2803 169 937 170 2132 171 1839 172 1625 173 517 174 2048 175 1679 176 2605 177 1213 178 1057 179 535 180 3134 181 541 182 2159 183 1255 184 2390 185 1369 186 2198 187 1219 188 1781 189 2397 190 2426 191 571 192 3304 193 577 194 1153 195 2391 196 2794 197 589 198 3060 199 595 200 3164 201 1381 202 1201 203 1507 204 3213 205 1525 206 1225 207 2283 208 3181 209 1405 210 3584 211 631 212 2015 213 1465 214 1273 215 1603 216 3912 217 1621 218 1297 219 1507 220 3430 221 1381 222 2648 223 667 224 3658 225 3173 226 1345 227 679 228 3657 229 685 230 3014 231 2943 232 3074 233 697 234 3774 235 1759 236 2249 237 1633 238 2996 239 715 240 4619 241 721 242 2549 243 2943 244 2327 245 2393 246 2948 247 1603 248 3302 249 1717 250 3470 251 751 252 4737 253 1777 254 1513 255 3231 256 4096 257 769 258 3098 259 1963 260 4264 261 2949 262 1561 263 787 264 4876 265 1993 266 3434 267 1843 268 2561 269 805 270 4949 271 811 272 4312 273 3609 274 1633 275 3035 276 4545 277 829 278 1657 279 3171 280 5144 281 841 282 3398 283 847 284 2717 285 3705 286 3263 287 2191 288 5730 289 1633 290 3896 291 2011 292 2795 293 877 294 4899 295 2227 296 3986 297 3957 298 1777 299 2047 300 5855 301 2305 302 1801 303 2095 304 4936 305 2305 306 5130 307 919 308 5206 309 2137 310 4190 311 931 312 5950 313 937 314 1873 315 5147 316 3029 317 949 318 3848 319 2335 320 5993 321 2221 322 4310 323 1927 324 6291 325 3677 326 1945 327 2263 328 4442 329 2533 330 6188 331 991 332 3185 333 3837 334 1993 335 2539 336 6900 337 1009 338 3635 339 2347 340 5860 341 2521 342 5829 343 2863 344 4670 345 4653 346 2065 347 1039 348 5877 349 1045 350 5912 351 4947 352 6409 353 1057 354 4298 355 2695 356 3419 357 4869 358 2137 359 1075 360 7839 361 2053 362 2161 363 4251 364 6232 365 2773 366 4448 367 1099 368 6184 369 4281 370 5072 371 2875 372 6321 373 1117 374 4619 375 5255 376 5126 377 2713 378 7269 379 1135 380 6622 381 2641 382 2281 383 1147 384 7968 385 4733 386 2305 387 4503 388 3731 389 1165 390 7526 391 2515 392 7132 393 2725 394 2353 395 3007 396 8175 397 1189 398 2377 399 5463 400 7871 401 1201 402 4898 403 2935 404 3887 405 6785 406 5624 407 3079 408 8314 409 1225 410 5660 411 2851 412 3965 413 3217 414 7329 415 3163 416 7801 417 2893 418 5261 419 1255 420 9294 421 1261 422 2521 423 4947 424 5810 425 4889 426 5198 427 3331 428 4121 429 5469 430 5954 431 1291 432 9594 433 1297 434 6062 435 6075 436 4199 437 2713 438 5348 439 1315 440 8657 441 6865 442 5327 443 1327 444 7653 445 3397 446 2665 447 3103 448 8803 449 1345 450 9473 451 3451 452 4355 453 3145 454 2713 455 5867 456 9460 457 1369 458 2737 459 6855 460 8281 461 1381 462 9144 463 1387 464 8056 465 6549 466 2785 467 1399 468 10038 469 3673 470 6542 471 3271 472 6494 473 3637 474 5798 475 5459 476 8662 477 5613 478 2857 479 1435 480 11205 481 3601 482 2881 483 6759 484 7786 485 3709 486 9207 487 1459 488 6722 489 3397 490 8590 491 1471 492 8541 493 3397 494 6137 495 8735 496 8680 497 3901 498 6098 499 1495 500 9410 501 3481 502 3001 503 1507 504 11779 505 3865 506 6542 507 6111 508 4901 509 1525 510 10310 511 4015 512 9728 513 7773 514 3073 515 3943 516 8985 517 4009 518 7376 519 3607 520 10835 521 1561 522 9579 523 1567 524 5057 525 9101 526 3145 527 3691 528 12009 529 3037 530 7424 531 6279 532 9940 533 4045 534 6548 535 4099 536 7406 537 3733 538 3217 539 5851 540 12777 541 1621 542 3241 543 3775 544 10477 545 4177 546 11052 547 1639 548 5291 549 6501 550 9929 551 3703 552 11680 553 4357 554 3313 555 7971 556 5369 557 1669 558 10329 559 4267 560 12601 561 7833 562 3361 563 1687 564 9873 565 4333 566 3385 567 9595 568 7862 569 1705 570 11852 571 1711 572 9988 573 3985 574 8252 575 6527 576 13784 577 1729 578 6383 579 4027 580 10855 581 4585 582 7148 583 4567 584 8090 585 10493 586 3505 587 1759 588 13063 589 4033 590 8306 591 4111 592 10552 593 1777 594 12411 595 8063 596 5759 597 4153 598 7685 599 1795 600 14559 601 1801 602 8690 603 7167 604 5837 605 7121 606 7448 607 1819 608 12085 609 8937 610 8600 611 4711 612 13710 613 1837 614 3673 615 8919 616 13204 617 1849 618 7598 619 1855 620 11713 621 9537 622 3721 623 4927 624 14613 625 7025 626 3745 627 8979 628 6071 629 4573 630 14947 631 1891 632 8774 633 4405 634 3793 635 4879 636 11205 637 7309 638 8720 639 7611 640 14342 641 1921 642 7898 643 1927 644 12424 645 9393 646 7529 647 1939 648 15668 649 5125 650 12242 651 9663 652 6305 653 1957 654 8048 655 5035 656 11800 657 7833 658 9566 659 1975 660 15888 661 1981 662 3961 663 9027 664 9230 665 9125 666 12579 667 4243 668 6461 669 4657 670 9482 671 5311 672 16603 673 2017 674 4033 675 13103 676 11218 677 2029 678 8348 679 5383 680 14831 681 4741 682 9446 683 2047 684 15612 685 5269 686 10654 687 4783 688 12424 689 5377 690 14864 691 2071 692 6695 693 12781 694 4153 695 5347 696 15265 697 5161 698 4177 699 4867 700 15895 701 2101 702 15327 703 5023 704 15434 705 10341 706 4225 707 5611 708 12537 709 2125 710 10070 711 8499 712 9914 713 4645 714 15129 715 9239 716 6929 717 4993 718 4297 719 2155 720 18980 721 5725 722 8045 723 5035 724 7007 725 8477 726 14175 727 2179 728 15694 729 11421 730 10364 731 5455 732 12981 733 2197 734 4393 735 13459 736 15229 737 5869 738 14079 739 2215 740 14287 741 10449 742 10880 743 2227 744 16483 745 5737 746 4465 747 8943 748 14032 749 5953 750 16730 751 2251 752 13672 753 5245 754 10088 755 5815 756 19102 757 2269 758 4537 759 11199 760 16649 761 2281 762 9398 763 6067 764 7397 765 14333 766 4585 767 6043 768 18896 769 2305 770 16066 771 5371 772 7475 773 2317 774 14829 775 9203 776 10826 777 11841 778 4657 779 5683 780 19485 781 6241 782 9749 783 12231 784 17461 785 6049 786 9698 787 2359 788 7631 789 5497 790 11246 791 6295 792 20222 793 6265 794 4753 795 11763 796 7709 797 2389 798 17109 799 6043 800 19055 801 9609 802 4801 803 6427 804 14313 805 11177 806 10958 807 5623 808 11282 809 2425 810 19674 811 2431 812 16057 813 5665 814 11624 815 6283 816 20250 817 6013 818 4897 819 15775 820 16003 821 2461 822 10148 823 2467 824 11510 825 15809 826 12194 827 2479 828 19788 829 2485 830 11834 831 5791 832 18698 833 10153 834 10298 835 6439 836 15874 837 13257 838 5017 839 2515 840 22786 841 4873 842 5041 843 5875 844 8177 845 10421 846 16329 847 9319 848 15544 849 5917 850 16958 851 5851 852 15201 853 2557 854 12632 855 16583 856 11966 857 2569 858 18219 859 2575 860 16861 861 13293 862 5161 863 2587 864 22997 865 6673 866 5185 867 10839 868 17383 869 6985 870 19202 871 6931 872 12194 873 10497 874 10601 875 12647 876 15645 877 2629 878 5257 879 6127 880 21194 881 2641 882 20509 883 2647 884 16438 885 13185 886 5305 887 2659 888 20137 889 7093 890 12716 891 15699 892 8645 893 6673 894 11048 895 6907 896 20834 897 13221 898 5377 899 5383 900 24174 901 6925 902 13076 903 14019 904 12650 905 6985 906 11198 907 2719 908 8801 909 10941 910 19516 911 2731 912 23172 913 7357 914 5473 915 13659 916 8879 917 7321 918 20820 919 2755 920 20933 921 6421 922 5521 923 7375 924 23803 925 11381 926 5545 927 11163 928 19765 929 2785 930 20693 931 11539 932 9035 933 6505 934 5593 935 13403 936 24767 937 2809 938 13946 939 6547 940 18577 941 2821 942 11648 943 6655 944 17416 945 20965 946 13802 947 2839 948 16977 949 7597 950 19136 951 6631 952 21925 953 2857 954 18579 955 7375 956 9269 957 14349 958 5737 959 7663 960 26693 961 5581 962 13568 963 11607 964 9347 965 7453 966 21345 967 2899 968 20444 969 12813 970 13892 971 2911 972 24624 973 7777 974 5833 975 18755 976 18040 977 2929 978 12098 979 7915 980 23608 981 11829 982 5881 983 2947 984 22573 985 7609 986 12899 987 15471 988 18868 989 7057 990 25611 991 2971 992 21229 993 6925 994 14822 995 7687 996 17865 997 2989 998 5977 999 16335 1000 23485