1 1 2 5 3 3 4 6 5 8 6 10 7 18 8 17 9 30 10 41 11 28 12 43 13 29 14 33 15 43 16 27 17 66 18 47 19 98 20 105 21 155 22 114 23 113 24 100 25 49 26 62 27 118 28 146 29 85 30 125 31 80 32 117 33 74 34 101 35 167 36 137 37 168 38 282 39 176 40 287 41 129 42 178 43 151 44 140 45 163 46 139 47 262 48 267 49 277 50 234 51 285 52 188 53 203 54 163 55 192 56 239 57 188 58 241 59 252 60 252 61 316 62 232 63 282 64 380 65 217 66 241 67 289 68 234 69 276 70 338 71 302 72 303 73 347 74 328 75 310 76 346 77 335 78 283 79 248 80 371 81 352 82 390 83 398 84 452 85 273 86 369 87 338 88 494 89 552 90 490 91 721 92 349 93 368 94 588 95 445 96 436 97 507 98 406 99 416 100 372 101 765 102 581 103 413 104 441 105 520 106 584 107 541 108 575 109 538 110 504 111 429 112 472 113 692 114 550 115 503 116 426 117 359 118 761 119 799 120 664 121 520 122 765 123 506 124 567 125 693 126 475 127 699 128 572 129 547 130 804 131 591 132 805 133 732 134 707 135 536 136 852 137 720 138 566 139 679 140 792 141 1109 142 694 143 554 144 831 145 550 146 855 147 774 148 721 149 730 150 710 151 733 152 837 153 662 154 934 155 811 156 638 157 828 158 1173 159 901 160 946 161 1047 162 588 163 871 164 976 165 707 166 1005 167 981 168 712 169 998 170 758 171 843 172 637 173 879 174 1141 175 657 176 890 177 1003 178 1265 179 1012 180 877 181 1001 182 998 183 1188 184 757 185 981 186 1061 187 1667 188 1016 189 1135 190 1050 191 1020 192 1150 193 978 194 1029 195 713 196 1228 197 1071 198 1328 199 996 200 1234 201 965 202 1145 203 925 204 936 205 1392 206 1215 207 955 208 927 209 1600 210 1717 211 2066 212 943 213 1345 214 1938 215 1075 216 1367 217 1186 218 1068 219 1286 220 1265 221 1327 222 962 223 1675 224 986 225 885 226 1118 227 1228 228 1865 229 1104 230 889 231 1071 232 1325 233 1328 234 1192 235 1376 236 1328 237 1173 238 2369 239 1676 240 1095 241 1093 242 1332 243 1817 244 1482 245 1234 246 1907 247 1103 248 1064 249 1532 250 1362 251 2169 252 1782 253 1422 254 1964 255 1667 256 1415 257 2198 258 1661 259 1150 260 1824 261 1074 262 1676 263 2357 264 1419 265 2323 266 2324 267 1800 268 1230 269 1658 270 1489 271 1422 272 1701 273 1085 274 1800 275 1430 276 1655 277 1967 278 1499 279 1925 280 2687 281 1916 282 1604 283 1959 284 1388 285 1759 286 2671 287 1661 288 1923 289 1199 290 2878 291 1471 292 2293 293 1813 294 2159 295 2001 296 1935 297 1831 298 1699 299 1851 300 2043 301 1946 302 1745 303 1874 304 1694 305 2098 306 1837 307 3867 308 1946 309 1857 310 2301 311 2875 312 2826 313 1760 314 1413 315 1782 316 2493 317 1524 318 1619 319 1784 320 3306 321 2028 322 1536 323 2029 324 2252 325 1505 326 2289 327 2045 328 2834 329 1957 330 2331 331 1910 332 2360 333 1736 334 2326 335 1940 336 1939 337 1323 338 2244 339 1597 340 3301 341 2490 342 1665 343 1980 344 2589 345 2350 346 1536 347 3515 348 2966 349 2622 350 1896 351 2018 352 2043 353 2098 354 2001 355 2593 356 2155 357 2155 358 2136 359 2482 360 2053 361 2060 362 2196 363 1945 364 2068 365 2267 366 3842 367 3233 368 1633 369 2829 370 2133 371 2666 372 3296 373 2394 374 1905 375 1861 376 1879 377 2096 378 1847 379 2108 380 1924 381 2542 382 2288 383 2469 384 1687 385 2455 386 2518 387 4689 388 2426 389 2494 390 2807 391 2193 392 3193 393 3066 394 2646 395 2987 396 2401 397 2601 398 2598 399 2109 400 2760 401 2539 402 2486 403 2624 404 2312 405 3044 406 2122 407 2430 408 4613 409 2505 410 2975 411 2376 412 2085 413 2510 414 3291 415 3002 416 2189 417 3746 418 2447 419 3005 420 2655 421 2714 422 2836 423 2481 424 2604 425 2586 426 3148 427 3341 428 3259 429 3012 430 2746 431 4701 432 2401 433 3000 434 2541 435 3026 436 2194 437 2551 438 3221 439 3209 440 2199 441 2809 442 2922 443 2405 444 2977 445 3988 446 3131 447 3004 448 2906 449 3180 450 2737 451 2628 452 2858 453 2325 454 2644 455 2400 456 2543 457 2633 458 4003 459 2719 460 2894 461 2745 462 3131 463 2837 464 2490 465 2907 466 4503 467 3425 468 3729 469 3462 470 3509 471 2830 472 2388 473 4794 474 2333 475 3092 476 3008 477 3833 478 2618 479 3364 480 3779 481 2881 482 3768 483 3200 484 3040 485 3392 486 3565 487 3198 488 2744 489 3042 490 2999 491 3292 492 3326 493 2736 494 4296 495 3747 496 2828 497 3729 498 4420 499 2984 500 2696 501 2388 502 5267 503 3394 504 3523 505 2959 506 3952 507 2628 508 2960 509 3360 510 3424 511 3886 512 2494 513 3051 514 3688 515 2703 516 3621 517 4596 518 3022 519 3912 520 4147 521 3665 522 2934 523 3250 524 3009 525 3984 526 2855 527 4531 528 3821 529 4140 530 4159 531 3208 532 3541 533 2685 534 4116 535 4072 536 3684 537 2862 538 4989 539 4186 540 3259 541 4098 542 2815 543 3574 544 4557 545 3712 546 2544 547 3320 548 3386 549 3135 550 5371 551 3102 552 3791 553 2588 554 4116 555 3307 556 4932 557 4301 558 4008 559 4873 560 4306 561 3695 562 4083 563 3543 564 3570 565 6416 566 4170 567 3690 568 3640 569 4698 570 5307 571 4386 572 3639 573 4297 574 3543 575 2970 576 3279 577 4107 578 3569 579 5053 580 4186 581 4143 582 3755 583 3765 584 5625 585 4073 586 3236 587 3271 588 3439 589 3571 590 3723 591 4001 592 6627 593 4733 594 4506 595 4432 596 4511 597 4888 598 3006 599 5666 600 3322 601 3553 602 4403 603 4120 604 4044 605 3410 606 3015 607 3830 608 4957 609 5346 610 4580 611 4512 612 5630 613 6527 614 4398 615 4330 616 4055 617 4942 618 4916 619 3466 620 4047 621 4974 622 4196 623 4162 624 4886 625 4836 626 4257 627 3018 628 4288 629 4759 630 3997 631 3247 632 3559 633 4831 634 3764 635 3591 636 3312 637 5019 638 4893 639 4865 640 3551 641 3391 642 3785 643 4425 644 4216 645 4454 646 4521 647 3770 648 3510 649 4763 650 4859 651 5607 652 4559 653 5682 654 3834 655 3969 656 4091 657 4505 658 3865 659 4761 660 5805 661 4600 662 4643 663 6663 664 5693 665 5865 666 5347 667 4047 668 4890 669 4519 670 5013 671 3991 672 6148 673 3816 674 4598 675 5726 676 5179 677 5487 678 5949 679 5449 680 5374 681 4275 682 4126 683 3754 684 5224 685 4542 686 5154 687 7638 688 4973 689 4877 690 4799 691 4636 692 4925 693 6544 694 5638 695 5271 696 7505 697 4992 698 4663 699 3794 700 5199 701 4190 702 5498 703 5602 704 4384 705 3943 706 5040 707 4292 708 5981 709 4246 710 7217 711 6231 712 3974 713 5866 714 5891 715 4411 716 6109 717 4566 718 3923 719 4596 720 5483 721 4745 722 6009 723 7036 724 4751 725 4413 726 5554 727 6682 728 4192 729 5470 730 4951 731 3928 732 5485 733 6283 734 5564 735 4766 736 5599 737 5404 738 5389 739 6777 740 4273 741 7092 742 5168 743 4344 744 5577 745 5989 746 5464 747 5368 748 5187 749 6468 750 6343 751 5032 752 4500 753 8145 754 4320 755 5982 756 5391 757 5193 758 7573 759 4872 760 4704 761 7006 762 5152 763 4897 764 5309 765 5914 766 5710 767 5262 768 4513 769 5384 770 5366 771 5324 772 5089 773 5060 774 5272 775 5266 776 5814 777 6111 778 4812 779 6860 780 5004 781 7814 782 6608 783 4659 784 7486 785 4893 786 6742 787 5760 788 4264 789 6732 790 6348 791 4417 792 5556 793 5725 794 5406 795 5488 796 5294 797 5692 798 5036 799 6835 800 4897 801 9330 802 6685 803 5655 804 5186 805 5345 806 5410 807 4989 808 7790 809 6057 810 5210 811 5697 812 4832 813 6190 814 6001 815 6545 816 6493 817 5378 818 6152 819 5326 820 6582 821 6245 822 5988 823 7745 824 6602 825 9222 826 5276 827 7730 828 6216 829 5493 830 5752 831 6155 832 5713 833 5883 834 7740 835 6291 836 5050 837 5508 838 5099 839 5016 840 7847 841 4687 842 5019 843 6443 844 5266 845 6437 846 8657 847 7077 848 6833 849 6875 850 6778 851 5234 852 6832 853 6066 854 5637 855 8463 856 5983 857 6033 858 4945 859 6843 860 5694 861 7055 862 5564 863 6329 864 7072 865 5732 866 8310 867 7678 868 6963 869 5026 870 5592 871 7765 872 6191 873 5321 874 6489 875 7124 876 5081 877 6719 878 4619 879 6580 880 5381 881 6533 882 6225 883 6084 884 7496 885 5124 886 6244 887 6458 888 5671 889 7531 890 6171 891 6948 892 7791 893 6827 894 7476 895 5135 896 7994 897 5185 898 9537 899 7158 900 5805 901 7061 902 6077 903 6255 904 7033 905 5532 906 7380 907 7345 908 9495 909 7005 910 6862 911 5972 912 7084 913 6287 914 6626 915 7219 916 5770 917 7305 918 6677 919 6222 920 6773 921 6321 922 5817 923 8702 924 7103 925 6237 926 5724 927 6217 928 6598 929 7201 930 7379 931 6364 932 7932 933 7116 934 6334 935 6445 936 8429 937 6567 938 5698 939 8337 940 6676 941 5421 942 5860 943 8707 944 5578 945 5860 946 8154 947 6484 948 7291 949 7489 950 7278 951 5172 952 6144 953 6476 954 6512 955 5887 956 7194 957 6795 958 8967 959 5368 960 6458 961 5485 962 6095 963 8624 964 7888 965 8059 966 7519 967 6502 968 6876 969 6755 970 7573 971 11703 972 8955 973 10723 974 6968 975 9780 976 10737 977 7239 978 6489 979 12151 980 8350 981 6507 982 8115 983 6845 984 8088 985 6371 986 8370 987 6727 988 7012 989 6945 990 8421 991 7212 992 5898 993 7179 994 7077 995 5694 996 8480 997 8149 998 7990 999 6962 1000 8056 1001 7966 1002 6571 1003 8098 1004 9983 1005 7388 1006 6474 1007 6919 1008 6516 1009 7640 1010 7484 1011 8374