1 1 2 4 3 5 4 10 5 15 6 24 7 17 8 28 9 27 10 60 11 31 12 36 13 81 14 70 15 71 16 68 17 117 18 96 19 37 20 120 21 81 22 100 23 139 24 192 25 97 26 176 27 123 28 174 29 205 30 128 31 193 32 126 33 137 34 220 35 201 36 216 37 133 38 196 39 397 40 296 41 189 42 396 43 321 44 256 45 305 46 280 47 331 48 396 49 445 50 292 51 313 52 256 53 481 54 556 55 417 56 326 57 553 58 256 59 685 60 480 61 487 62 260 63 387 64 326 65 481 66 516 67 661 68 352 69 315 70 436 71 801 72 586 73 667 74 772 75 513 76 588 77 629 78 936 79 481 80 880 81 663 82 436 83 511 84 864 85 661 86 664 87 417 88 520 89 541 90 456 91 731 92 480 93 567 94 746 95 733 96 774 97 1137 98 776 99 639 100 1180 101 991 102 1136 103 827 104 576 105 975 106 592 107 777 108 1376 109 859 110 1000 111 1011 112 1228 113 785 114 942 115 655 116 896 117 1119 118 902 119 889 120 1170 121 1441 122 592 123 1153 124 1302 125 1375 126 1176 127 1369 128 1104 129 1797 130 1168 131 1021 132 1282 133 1471 134 1324 135 1745 136 1024 137 1725 138 1746 139 1717 140 2056 141 1701 142 1376 143 1159 144 1614 145 1297 146 1552 147 1761 148 1496 149 2011 150 1710 151 1501 152 1776 153 1737 154 1680 155 1615 156 1976 157 1327 158 1040 159 1953 160 1400 161 1741 162 1240 163 2431 164 1796 165 1825 166 1636 167 1831 168 1344 169 1681 170 2352 171 1593 172 2056 173 2451 174 1392 175 2611 176 2552 177 1941 178 1796 179 1963 180 2508 181 2353 182 2106 183 1821 184 2344 185 2867 186 1672 187 1861 188 1684 189 1881 190 2400 191 1537 192 2468 193 2551 194 2396 195 1771 196 2464 197 1681 198 1872 199 2913 200 2406 201 2849 202 2746 203 2965 204 1920 205 1973 206 1676 207 1935 208 2416 209 2017 210 3420 211 2785 212 2336 213 2643 214 3478 215 2435 216 2016 217 2245 218 1696 219 3677 220 3084 221 2881 222 2292 223 3073 224 2728 225 2143 226 3124 227 1961 228 2078 229 2179 230 2800 231 2541 232 3220 233 2851 234 2976 235 3199 236 3070 237 3729 238 2704 239 2857 240 3100 241 2189 242 2296 243 3207 244 2296 245 3137 246 2870 247 4225 248 2856 249 3963 250 4076 251 3277 252 2816 253 3575 254 3040 255 417 256 2476 257 1561 258 2274 259 1661 260 1504 261 2103 262 2622 263 1141 264 1764 265 1537 266 1168 267 1681 268 2776 269 1369 270 1820 271 1561 272 2572 273 1257 274 2866 275 1489 276 1134 277 1189 278 868 279 1881 280 910 281 1071 282 1986 283 1563 284 1276 285 1983 286 506 287 3745 288 2416 289 1561 290 1392 291 1961 292 632 293 2065 294 1556 295 3361 296 1936 297 2031 298 2124 299 2553 300 1686 301 1225 302 3288 303 1809 304 2874 305 3655 306 1584 307 2613 308 3532 309 3353 310 1372 311 2195 312 3292 313 2081 314 2998 315 1869 316 3880 317 4265 318 3236 319 2497 320 1696 321 471 322 1336 323 1621 324 2466 325 3353 326 2176 327 1467 328 3910 329 1755 330 3340 331 1681 332 4052 333 3831 334 2234 335 3625 336 2330 337 1345 338 1232 339 2361 340 2932 341 2017 342 3648 343 1173 344 1786 345 3985 346 4036 347 3181 348 2634 349 1751 350 2500 351 1521 352 2728 353 4421 354 2616 355 3961 356 3992 357 1329 358 2786 359 2913 360 4162 361 2461 362 2696 363 3831 364 1620 365 1255 366 1488 367 4585 368 2278 369 1521 370 2500 371 4291 372 2418 373 2921 374 2176 375 2025 376 1248 377 2031 378 3888 379 1281 380 3568 381 1741 382 2048 383 1759 384 4960 385 2719 386 3114 387 3261 388 2368 389 3373 390 2126 391 2017 392 5328 393 2493 394 3052 395 3415 396 2592 397 1225 398 2392 399 1491 400 1900 401 4597 402 3024 403 2173 404 3384 405 3413 406 3646 407 2293 408 4496 409 3421 410 5098 411 3969 412 5732 413 2401 414 2916 415 5665 416 3536 417 2535 418 4540 419 2977 420 3820 421 4161 422 2440 423 6059 424 2874 425 4705 426 3576 427 5341 428 3648 429 3861 430 2210 431 3121 432 3026 433 3319 434 1914 435 2385 436 3136 437 6601 438 3996 439 3943 440 3178 441 3683 442 5392 443 5329 444 6396 445 5905 446 4496 447 3141 448 4342 449 3745 450 3720 451 4501 452 1596 453 5315 454 4816 455 4849 456 5776 457 3493 458 4696 459 4053 460 4856 461 3625 462 1356 463 3299 464 6616 465 3597 466 5344 467 5245 468 2154 469 4785 470 5650 471 6201 472 3686 473 5147 474 5616 475 7005 476 3604 477 2885 478 2716 479 2421 480 4688 481 7033 482 4104 483 6993 484 3656 485 5323 486 5046 487 2197 488 5406 489 2451 490 5170 491 6001 492 3772 493 5569 494 5156 495 5207 496 7276 497 5569 498 3396 499 7039 500 2860 501 6861 502 7288 503 4833 504 4986 505 2773 506 5456 507 5525 508 2656 509 4801 510 6222 511 7721 512 3896 513 7425 514 6016 515 4075 516 5952 517 5921 518 7600 519 6033 520 5020 521 4777 522 6318 523 5761 524 7750 525 5745 526 3434 527 3121 528 7528 529 5057 530 5440 531 6399 532 4704 533 3697 534 7786 535 6313 536 3208 537 3285 538 3896 539 5617 540 6210 541 3141 542 4096 543 6747 544 5132 545 4337 546 3696 547 4777 548 8624 549 4191 550 6764 551 7201 552 4554 553 7879 554 4016 555 4041 556 6436 557 4645 558 4976 559 5311 560 4096 561 4921 562 5738 563 6171 564 8364 565 3445 566 4966 567 3519 568 5056 569 5849 570 6558 571 7729 572 7084 573 6777 574 7792 575 7225 576 5836 577 9793 578 4894 579 5273 580 6880 581 6641 582 5748 583 9661 584 6994 585 7125 586 6036 587 8641 588 6644 589 6993 590 6784 591 6759 592 10496 593 4033 594 6844 595 6733 596 6034 597 8281 598 8616 599 9573 600 8504 601 5801 602 9046 603 8721 604 10630 605 6275 606 9320 607 6699 608 8576 609 6183 610 7148 611 3223 612 6816 613 9377 614 9574 615 6847 616 6860 617 7189 618 9696 619 9709 620 4462 621 6561 622 10576 623 6865 624 7176 625 5241 626 8182 627 6149 628 5672 629 4081 630 5232 631 9451 632 10368 633 6159 634 6626 635 8453 636 7616 637 5167 638 10432 639 9753 640 8250 641 6691 642 9240 643 6833 644 8680 645 10713 646 7302 647 5281 648 9264 649 10705 650 8380 651 4941 652 7566 653 9321 654 10032 655 7549 656 9532 657 4627 658 8156 659 6109 660 7408 661 3707 662 6286 663 5553 664 5006 665 5329 666 9436 667 6823 668 9088 669 10119 670 7748 671 9089 672 6936 673 4581 674 8560 675 10431 676 4926 677 10159 678 12420 679 6041 680 8552 681 4257 682 8176 683 6265 684 11664 685 9037 686 9990 687 10753 688 7996 689 7021 690 8862 691 8285 692 6352 693 4473 694 6826 695 10735 696 9120 697 9265 698 6916 699 5057 700 11508 701 8881 702 7328 703 4555 704 8636 705 11421 706 5904 707 13369 708 6846 709 8821 710 8632 711 8529 712 8502 713 9589 714 9516 715 8777 716 9130 717 6021 718 9160 719 9601 720 12654 721 11017 722 11536 723 14109 724 11170 725 7459 726 6776 727 9031 728 11316 729 9829 730 9760 731 6973 732 6066 733 10345 734 7240 735 5505 736 9080 737 6121 738 8206 739 12193 740 8014 741 10881 742 9064 743 8151 744 5256 745 5849 746 10000 747 9837 748 10042 749 8305 750 8580 751 9601 752 11536 753 8105 754 6376 755 9885 756 11268 757 13813 758 13516 759 9111 760 8770 761 7041 762 7742 763 14853 764 12976 765 10119 766 10126 767 5959 768 6456 769 9571 770 12112 771 10461 772 10796 773 10621 774 12914 775 13225 776 13264 777 6919 778 9724 779 12435 780 9552 781 14161 782 12236 783 8087 784 9772 785 12955 786 11504 787 14377 788 12736 789 10813 790 14908 791 9307 792 8712 793 10669 794 10176 795 16125 796 10756 797 9361 798 13176 799 9911 800 11104 801 10579 802 12316 803 13393 804 11744 805 9833 806 11542 807 13925 808 16756 809 11281 810 12100 811 8929 812 12346 813 10145 814 11598 815 8417 816 10356 817 15697 818 8506 819 10023 820 10900 821 6331 822 10068 823 6985 824 9704 825 10593 826 16954 827 10801 828 15602 829 9481 830 17146 831 10773 832 15820 833 12433 834 14472 835 11725 836 7102 837 14353 838 11086 839 13105 840 10160 841 9841 842 13616 843 7481 844 14080 845 12373 846 7506 847 14329 848 14092 849 7937 850 13720 851 10225 852 11636 853 13251 854 12340 855 13443 856 15052 857 17157 858 10614 859 10201 860 9952 861 10647 862 15568 863 11521 864 12116 865 11587 866 11272 867 11243 868 10660 869 12769 870 7840 871 11995 872 12120 873 12741 874 10186 875 9553 876 11644 877 10327 878 8162 879 12825 880 12896 881 11521 882 12688 883 15687 884 12784 885 15765 886 8008 887 12751 888 13032 889 14141 890 12944 891 9553 892 13924 893 14445 894 11616 895 11191 896 6626 897 10433 898 17744 899 16261 900 8640 901 11601 902 9884 903 18613 904 13138 905 14791 906 9636 907 9601 908 18496 909 13663 910 13398 911 12729 912 13536 913 15677 914 13432 915 12325 916 16864 917 10201 918 12120 919 11665 920 10156 921 7991 922 17608 923 13153 924 15900 925 10069 926 17050 927 14055 928 20024 929 11735 930 17424 931 17343 932 19048 933 19881 934 14726 935 15289 936 14224 937 12811 938 16288 939 17361 940 15700 941 15241 942 20200 943 13401 944 13280 945 15225 946 13168 947 19801 948 12708 949 17329 950 17098 951 8937 952 16076 953 15599 954 16328 955 13489 956 13776 957 17985 958 12244 959 14619 960 19440 961 16165 962 17480 963 12873 964 16816 965 11455 966 21966 967 11451 968 17596 969 18753 970 8810 971 16209 972 9612 973 14441 974 15376 975 15129 976 14696 977 15925 978 5662 979 14185 980 9010 981 4485 982 9496 983 8377 984 11848 985 8401 986 2632 987 5185 988 13664 989 20311 990 8072 991 10721 992 17676 993 15597 994 10000 995 14001 996 4278 997 4575 998 9316 999 12351 1000 6476