1 1 2 3 3 95 4 8 5 22 6 121 7 144 8 24 9 27 10 60 11 67 12 73 13 66 14 79 15 163 16 196 17 148 18 150 19 220 20 80 21 181 22 173 23 178 24 197 25 213 26 203 27 194 28 202 29 261 30 374 31 304 32 387 33 645 34 295 35 447 36 379 37 290 38 420 39 362 40 506 41 515 42 878 43 520 44 836 45 941 46 495 47 594 48 754 49 884 50 958 51 501 52 485 53 561 54 407 55 467 56 549 57 455 58 523 59 538 60 581 61 630 62 579 63 543 64 516 65 551 66 713 67 643 68 641 69 677 70 692 71 611 72 1124 73 661 74 973 75 969 76 934 77 1006 78 771 79 1147 80 935 81 1037 82 963 83 1015 84 1049 85 1096 86 1359 87 1176 88 1202 89 1265 90 1341 91 1209 92 1330 93 1283 94 1432 95 1048 96 1488 97 1235 98 1396 99 1376 100 1492 101 1405 102 1253 103 1384 104 1184 105 1482 106 1416 107 1595 108 1256 109 1335 110 1353 111 1552 112 1527 113 1267 114 1658 115 1667 116 1584 117 1694 118 1885 119 1580 120 2282 121 1631 122 1671 123 2283 124 1567 125 1489 126 1581 127 1946 128 1274 129 1374 130 2417 131 1410 132 1380 133 1473 134 1448 135 1421 136 2796 137 1375 138 2454 139 1840 140 1470 141 1465 142 1622 143 1559 144 1554 145 1566 146 1660 147 1647 148 1650 149 1429 150 2921 151 1511 152 1496 153 1725 154 1695 155 2771 156 2100 157 1600 158 1601 159 2629 160 1704 161 1632 162 2500 163 1561 164 2086 165 2394 166 1606 167 1999 168 1922 169 1836 170 1742 171 3287 172 2184 173 1997 174 3085 175 2084 176 2722 177 2591 178 1935 179 2272 180 3115 181 1902 182 2780 183 2486 184 2757 185 2075 186 3152 187 2593 188 2526 189 2762 190 2368 191 2633 192 2329 193 2292 194 3327 195 3207 196 3420 197 2894 198 2610 199 3306 200 3217 201 2647 202 2889 203 3174 204 3292 205 3412 206 3029 207 4128 208 2506 209 3377 210 2964 211 2867 212 3559 213 3173 214 3105 215 3510 216 4405 217 3284 218 3421 219 3542 220 3240 221 3346 222 3483 223 3585 224 3700 225 3266 226 3647 227 3341 228 4380 229 3839 230 3366 231 3392 232 3390 233 3355 234 3546 235 3842 236 3616 237 3829 238 3467 239 3376 240 3480 241 3411 242 3744 243 3294 244 3497 245 3823 246 3537 247 3739 248 3787 249 3389 250 3484 251 3696 252 4167 253 3728 254 3536 255 3752 256 3590 257 3658 258 3612 259 3623 260 3865 261 3561 262 3674 263 3783 264 3611 265 3872 266 4330 267 3711 268 4324 269 3891 270 4180 271 3801 272 4485 273 4072 274 3909 275 3719 276 4119 277 3896 278 3992 279 3954 280 3971 281 3785 282 3782 283 4059 284 3956 285 4501 286 3982 287 4131 288 4088 289 3887 290 3868 291 3975 292 3766 293 3892 294 3983 295 4136 296 4092 297 4275 298 5937 299 4137 300 3826 301 4222 302 4531 303 3734 304 4148 305 4043 306 4296 307 4559 308 4764 309 4298 310 4306 311 4483 312 4456 313 4289 314 5312 315 7397 316 4203 317 6340 318 4446 319 4139 320 4095 321 6197 322 5630 323 5173 324 4674 325 4176 326 7315 327 4351 328 4291 329 3878 330 5160 331 5466 332 5241 333 6907 334 5360 335 4129 336 4644 337 4529 338 4667 339 4506 340 4448 341 4834 342 4857 343 4204 344 5132 345 4972 346 4685 347 5753 348 4385 349 4335 350 5377 351 5004 352 4833 353 5635 354 6310 355 5053 356 5144 357 4280 358 5239 359 4814 360 4690 361 5364 362 5705 363 4878 364 5175 365 5923 366 5016 367 5073 368 4530 369 4439 370 5651 371 6985 372 4971 373 6794 374 4887 375 4626 376 4860 377 4784 378 7010 379 4386 380 4361 381 6003 382 6313 383 5146 384 7959 385 4757 386 4577 387 5879 388 5135 389 7350 390 6209 391 7645 392 6214 393 6982 394 6172 395 7220 396 5277 397 5506 398 7559 399 9103 400 8917 401 6669 402 7544 403 7418 404 6627 405 6541 406 7026 407 7588 408 8581 409 5983 410 9429 411 9109 412 7773 413 9079 414 8390 415 7101 416 8136 417 7642 418 8759 419 5169 420 8516 421 9194 422 9932 423 5851 424 8665 425 6037 426 7111 427 8378 428 8859 429 8594 430 9228 431 8711 432 9257 433 8189 434 8807 435 8269 436 8666 437 9202 438 8037 439 8906 440 8668 441 7253 442 8953 443 8557 444 9391 445 8720 446 8977 447 9361 448 8493 449 8432 450 9083 451 7653 452 8571 453 8912 454 9351 455 9042 456 9046 457 6015 458 8000 459 9981 460 8535 461 9477 462 9354 463 8820 464 9121 465 8902 466 8858 467 8879 468 8639 469 9756 470 9268 471 8809 472 9139 473 8386 474 9119 475 9673 476 9812 477 9478 478 10448 479 9386 480 9687 481 9273 482 9314 483 9238 484 9364 485 9465 486 8366 487 9731 488 9140 489 10674 490 10041 491 8950 492 9176 493 10618 494 9359 495 8762 496 9524 497 9343 498 9533 499 9556 500 9188 501 6446 502 8757 503 9034 504 9834 505 9963 506 9410 507 9630 508 10260 509 10274 510 9568 511 9534 512 9309 513 9732 514 9497 515 9913 516 9894 517 16286 518 10509 519 10861 520 9740 521 9479 522 10741 523 10018 524 10551 525 19120 526 8935 527 9893 528 11468 529 11628 530 9327 531 8951 532 11410 533 9502 534 9886 535 9535 536 10437 537 9304 538 9612 539 19432 540 10226 541 11276 542 9653 543 9029 544 8772 545 10179 546 10450 547 10407 548 9792 549 9527 550 9999 551 10530 552 11405 553 10455 554 11021 555 9288 556 10642 557 9787 558 9734 559 9207 560 11237 561 9726 562 10300 563 10573 564 10188 565 9763 566 10006 567 10342 568 9641 569 9260 570 12255 571 10137 572 12284 573 10245 574 15128 575 10736 576 16388 577 10960 578 9855 579 8787 580 10012 581 9229 582 9772 583 10849 584 10133 585 9365 586 9651 587 9708 588 11345 589 10091 590 9532 591 9818 592 10033 593 10487 594 9935 595 11658 596 10019 597 10191 598 10885 599 9867 600 10214 601 9559 602 9344 603 10395 604 9546 605 10682 606 9592 607 10289 608 9840 609 10076 610 9975 611 10195 612 10165 613 9680 614 9896 615 9489 616 9587 617 9848 618 9615 619 9723 620 10206 621 9645 622 10944 623 9398 624 10923 625 10138 626 10312 627 9733 628 10160 629 10065 630 9833 631 10020 632 9852 633 9475 634 10714 635 9483 636 10519 637 9712 638 10430 639 10791 640 10058 641 9971 642 9665 643 9841 644 10290 645 9930 646 10040 647 10308 648 10026 649 9801 650 9624 651 10710 652 10921 653 9857 654 9953 655 10456 656 10473 657 9805 658 10059 659 10302 660 10205 661 10469 662 10435 663 10754 664 10025 665 10493 666 11119 667 9972 668 11203 669 10099 670 10588 671 10088 672 10332 673 10597 674 10993 675 10064 676 10299 677 11123 678 9950 679 10520 680 11751 681 10055 682 11287 683 10268 684 10345 685 10313 686 13020 687 10476 688 9758 689 10070 690 10333 691 10513 692 10610 693 9938 694 10365 695 11695 696 10401 697 11406 698 10152 699 10317 700 10331 701 10818 702 10672 703 11527 704 10743 705 10688 706 10027 707 11753 708 10627 709 11338 710 10700 711 11350 712 10755 713 11851 714 11596 715 10463 716 10716 717 11074 718 13427 719 10808 720 11134 721 11577 722 10557 723 11223 724 11017 725 10277 726 10830 727 10886 728 11316 729 10369 730 11031 731 11135 732 10446 733 11361 734 10789 735 11743 736 11260 737 11804 738 10814 739 11091 740 10620 741 11246 742 10870 743 11173 744 10913 745 11434 746 11459 747 11696 748 11171 749 13142 750 11456 751 11297 752 10946 753 11538 754 11381 755 14711 756 11082 757 11122 758 12578 759 11336 760 11286 761 11714 762 11911 763 11870 764 10798 765 11014 766 12137 767 11271 768 11509 769 11519 770 11308 771 11881 772 11829 773 11312 774 12115 775 11661 776 10963 777 11362 778 11818 779 11132 780 15165 781 11746 782 11896 783 13628 784 12305 785 11904 786 11501 787 12704 788 11236 789 12323 790 12114 791 12346 792 11932 793 13389 794 11584 795 13477 796 11858 797 12120 798 11993 799 12960 800 13495 801 13558 802 12416 803 12650 804 14310 805 14598 806 12178 807 12148 808 13550 809 15507 810 12875 811 11742 812 13398 813 12170 814 18880 815 15047 816 14907 817 17984 818 14397 819 12483 820 17831 821 16365 822 13638 823 15898 824 13469 825 17002 826 12176 827 12845 828 11738 829 15152 830 16529 831 17370 832 12792 833 20165 834 12203 835 18687 836 18364 837 12399 838 21423 839 15154 840 16603 841 16495 842 13411 843 16386 844 17094 845 16071 846 12917 847 20979 848 17402 849 17519 850 18725 851 15062 852 17189 853 17759 854 17138 855 17765 856 18650 857 20880 858 18856 859 18803 860 18970 861 18313 862 17860 863 20593 864 15989 865 18131 866 17579 867 18271 868 12138 869 12986 870 16548 871 18042 872 17095 873 19874 874 19069 875 18099 876 18396 877 16980 878 18390 879 19147 880 20549 881 18653 882 18294 883 15743 884 20446 885 18849 886 17254 887 18601 888 18729 889 16023 890 17662 891 12979 892 19927 893 21442 894 18402 895 18174 896 20290 897 19467 898 19891 899 17982 900 18823 901 19701 902 21819 903 22101 904 21567 905 17684 906 18738 907 20242 908 18850 909 20893 910 20597 911 17541 912 18717 913 19777 914 16322 915 17617 916 19073 917 17974 918 18221 919 18782 920 17537 921 22354 922 18907 923 19969 924 22622 925 23396 926 21108 927 20717 928 22680 929 19131 930 20500 931 19395 932 19964 933 22583 934 18413 935 21196 936 21342 937 23792 938 23836 939 20083 940 18251 941 21441 942 19858 943 21868 944 16771 945 23325 946 22631 947 21816 948 23881 949 21900 950 23029 951 22077 952 23210 953 22214 954 19365 955 21880 956 22429 957 22575 958 21955 959 20563 960 23108 961 21743 962 18307 963 22722 964 21797 965 24255 966 21960 967 21817 968 21398 969 22813 970 23237 971 24317 972 23440 973 23486 974 23203 975 24168 976 24224 977 21596 978 22394 979 22884 980 25796 981 24217 982 23963 983 23187 984 21902 985 24071 986 21884 987 23615 988 20852 989 22164 990 22143 991 22802 992 24239 993 25355 994 24262 995 23690 996 24981 997 23914 998 23964 999 24223 1000 22437