1 2 2 6 3 3 4 3 5 6 6 6 7 12 8 48 9 33 10 48 11 30 12 48 13 42 14 51 15 93 16 87 17 75 18 111 19 111 20 132 21 114 22 141 23 156 24 150 25 150 26 156 27 183 28 213 29 240 30 201 31 210 32 222 33 192 34 210 35 258 36 249 37 312 38 267 39 282 40 348 41 300 42 336 43 375 44 312 45 372 46 390 47 381 48 363 49 366 50 411 51 363 52 366 53 375 54 399 55 447 56 516 57 501 58 501 59 492 60 534 61 579 62 519 63 555 64 561 65 606 66 573 67 600 68 600 69 705 70 606 71 672 72 660 73 660 74 633 75 687 76 708 77 723 78 687 79 789 80 699 81 750 82 831 83 843 84 879 85 798 86 831 87 798 88 843 89 867 90 849 91 843 92 894 93 885 94 798 95 969 96 993 97 969 98 1011 99 957 100 957 101 1002 102 1005 103 993 104 1131 105 1059 106 996 107 1047 108 1077 109 1110 110 1038 111 1056 112 1074 113 1239 114 1140 115 1068 116 1218 117 1218 118 1203 119 1218 120 1185 121 1203 122 1212 123 1380 124 1275 125 1230 126 1245 127 1263 128 1347 129 1356 130 1383 131 1320 132 1326 133 1389 134 1452 135 1329 136 1419 137 1452 138 1434 139 1563 140 1497 141 1524 142 1545 143 1572 144 1569 145 1461 146 1644 147 1635 148 1605 149 1659 150 1599 151 1626 152 1686 153 1668 154 1716 155 1707 156 1632 157 1668 158 1788 159 1698 160 1767 161 1725 162 1785 163 1884 164 1770 165 1803 166 1851 167 1815 168 1914 169 1869 170 1740 171 1887 172 1887 173 1857 174 1884 175 2046 176 1950 177 1896 178 2118 179 1974 180 2100 181 2091 182 1995 183 2103 184 2154 185 2121 186 2073 187 2235 188 2172 189 2172 190 2184 191 2094 192 2271 193 2289 194 2229 195 2352 196 2355 197 2247 198 2220 199 2325 200 2391 201 2298 202 2361 203 2388 204 2469 205 2373 206 2496 207 2397 208 2445 209 2370 210 2469 211 2442 212 2490 213 2625 214 2397 215 2544 216 2490 217 2598 218 2577 219 2544 220 2568 221 2532 222 2514 223 2589 224 2589 225 2577 226 2667 227 2733 228 2658 229 2820 230 2787 231 2778 232 2787 233 2697 234 2757 235 2757 236 2751 237 2976 238 2874 239 2805 240 2892 241 2904 242 2886 243 2976 244 2931 245 2910 246 2913 247 3039 248 3072 249 2874 250 3093 251 3003 252 3018 253 3111 254 3039 255 3036 256 3174 257 3165 258 3192 259 3171 260 3198 261 3243 262 3192 263 3138 264 3129 265 3360 266 3171 267 3219 268 3288 269 3396 270 3471 271 3237 272 3399 273 3147 274 3354 275 3318 276 3453 277 3369 278 3441 279 3369 280 3525 281 3459 282 3477 283 3480 284 3408 285 3417 286 3432 287 3576 288 3489 289 3579 290 3657 291 3633 292 3657 293 3588 294 3648 295 3576 296 3813 297 3786 298 3765 299 3786 300 3867 301 3858 302 3756 303 4008 304 3930 305 3903 306 4056 307 3738 308 3927 309 3912 310 3975 311 3972 312 3732 313 4035 314 3918 315 3912 316 4020 317 4098 318 4092 319 4083 320 3909 321 4107 322 4116 323 4029 324 4137 325 3999 326 4044 327 4161 328 4143 329 4299 330 4251 331 4071 332 4245 333 4281 334 4242 335 4323 336 4299 337 4308 338 4431 339 4305 340 4269 341 4143 342 4389 343 4485 344 4395 345 4425 346 4593 347 4413 348 4368 349 4299 350 4485 351 4440 352 4692 353 4335 354 4614 355 4704 356 4665 357 4524 358 4782 359 4542 360 4683 361 4647 362 4605 363 4674 364 4821 365 4650 366 4776 367 4764 368 4872 369 4800 370 4659 371 4623 372 4845 373 4983 374 4803 375 4821 376 4953 377 5109 378 4911 379 4935 380 5052 381 4893 382 5079 383 5016 384 4938 385 5118 386 5052 387 5088 388 5070 389 5007 390 5091 391 5325 392 5232 393 5145 394 5262 395 5070 396 5034 397 5160 398 5343 399 5199 400 5250 401 5250 402 5280 403 5208 404 5457 405 5379 406 5388 407 5289 408 5475 409 5430 410 5415 411 5460 412 5385 413 5640 414 5235 415 5442 416 5511 417 5505 418 5586 419 5430 420 5523 421 5574 422 5538 423 5811 424 5763 425 5763 426 5622 427 5781 428 5550 429 5595 430 5880 431 5817 432 5811 433 5739 434 5961 435 5745 436 5694 437 5712 438 5937 439 5991 440 5811 441 5745 442 5874 443 6045 444 5997 445 5961 446 6027 447 6189 448 6042 449 6087 450 5934 451 6132 452 6045 453 5988 454 6045 455 6099 456 6258 457 6186 458 6072 459 5973 460 6222 461 6042 462 6141 463 6279 464 6171 465 6270 466 6279 467 6315 468 6330 469 6342 470 6396 471 6144 472 6384 473 6216 474 6486 475 6420 476 6492 477 6549 478 6504 479 6771 480 6531 481 6513 482 6465 483 6438 484 6441 485 6459 486 6699 487 6753 488 6837 489 6621 490 6585 491 6747 492 6537 493 6780 494 6630 495 6933 496 6861 497 6717 498 6576 499 6882 500 6819 501 6798 502 6735 503 6972 504 7071 505 6864 506 6915 507 7233 508 6891 509 7125 510 6720 511 6942 512 6990 513 6999 514 6942 515 7122 516 7014 517 7044 518 7287 519 7329 520 7194 521 7212 522 7320 523 7197 524 7284 525 7176 526 7197 527 7350 528 7167 529 7350 530 7329 531 7266 532 7440 533 7053 534 7509 535 7464 536 7611 537 7359 538 7266 539 7455 540 7761 541 7341 542 7392 543 7554 544 7593 545 7536 546 7428 547 7527 548 7656 549 7782 550 7626 551 7872 552 7791 553 7725 554 7791 555 7527 556 7761 557 7842 558 7746 559 7935 560 7890 561 7653 562 7827 563 7959 564 7671 565 7716 566 7725 567 7881 568 8025 569 8184 570 7773 571 8025 572 7878 573 7923 574 7986 575 8112 576 8061 577 8085 578 8130 579 7971 580 8232 581 8193 582 8319 583 8151 584 8085 585 8274 586 8304 587 8043 588 8193 589 8124 590 8385 591 8160 592 8211 593 8184 594 8628 595 8268 596 8475 597 8517 598 8376 599 8400 600 8520 601 8463 602 8346 603 8733 604 8427 605 8286 606 8823 607 8511 608 8571 609 8373 610 8484 611 8682 612 8628 613 8652 614 8688 615 8781 616 8823 617 8562 618 8733 619 8607 620 8646 621 8727 622 8718 623 9042 624 8862 625 8715 626 8976 627 8925 628 9048 629 8904 630 9093 631 9021 632 9006 633 8877 634 8934 635 9156 636 8925 637 9033 638 8961 639 9183 640 9357 641 9339 642 9024 643 9453 644 9372 645 9087 646 9372 647 9201 648 9354 649 9096 650 9267 651 9528 652 9210 653 9267 654 9264 655 9291 656 9093 657 9465 658 9453 659 9723 660 9393 661 9453 662 9471 663 9498 664 9393 665 9501 666 9597 667 9669 668 9651 669 9561 670 9690 671 9381 672 9696 673 9582 674 9528 675 9696 676 9825 677 9852 678 9699 679 9759 680 9906 681 9795 682 9876 683 10200 684 9876 685 9966 686 9780 687 9831 688 10110 689 9825 690 10086 691 9579 692 9885 693 9894 694 10065 695 9969 696 10086 697 9975 698 10122 699 10101 700 10077 701 10149 702 9993 703 9960 704 10200 705 10137 706 10005 707 10284 708 10218 709 10527 710 10164 711 10284 712 10317 713 10362 714 10335 715 10644 716 10356 717 10428 718 10644 719 10551 720 10389 721 10533 722 10428 723 10488 724 10254 725 10536 726 10452 727 10497 728 10464 729 10443 730 10533 731 10704 732 10725 733 10779 734 10491 735 10554 736 10821 737 10866 738 10644 739 10824 740 10659 741 10488 742 11046 743 11004 744 10851 745 10812 746 11082 747 11085 748 10689 749 10797 750 10974 751 11019 752 11175 753 10920 754 10992 755 10995 756 11247 757 10986 758 11058 759 11019 760 11019 761 11004 762 11118 763 11211 764 11130 765 11085 766 11229 767 11361 768 11418 769 11166 770 11517 771 11280 772 11166 773 11328 774 11208 775 11424 776 11526 777 11388 778 11154 779 11400 780 11559 781 11352 782 11751 783 11406 784 11496 785 11697 786 11640 787 11496 788 11676 789 11796 790 11613 791 11748 792 11478 793 11874 794 11904 795 11760 796 11685 797 11742 798 11643 799 11748 800 12027 801 11661 802 11787 803 11679 804 11964 805 11931 806 12039 807 12099 808 11892 809 11865 810 12129 811 12111 812 11931 813 11811 814 11760 815 12189 816 12063 817 12207 818 12021 819 12081 820 12081 821 12345 822 12594 823 11994 824 12198 825 12342 826 12117 827 12363 828 12198 829 12243 830 12387 831 12504 832 12225 833 12696 834 12507 835 12192 836 12309 837 12036 838 12180 839 12756 840 12714 841 12606 842 12432 843 12624 844 12606 845 12354 846 12603 847 12567 848 12525 849 12594 850 12792 851 12603 852 13002 853 12738 854 12900 855 12693 856 12963 857 12660 858 13098 859 12702 860 12468 861 12621 862 12849 863 12840 864 12738 865 13224 866 12864 867 12804 868 13083 869 13017 870 13101 871 13209 872 13098 873 12891 874 13110 875 12822 876 13134 877 13080 878 13191 879 13029 880 13305 881 13044 882 13119 883 13125 884 13272 885 12903 886 13245 887 13206 888 13368 889 13254 890 13242 891 13533 892 13308 893 13431 894 13521 895 13395 896 13434 897 13485 898 13218 899 13587 900 13470 901 13584 902 13308 903 13341 904 13296 905 13890 906 13839 907 13740 908 13650 909 13701 910 13614 911 13935 912 14109 913 13827 914 13584 915 13956 916 13893 917 13965 918 13890 919 13443 920 13758 921 13755 922 13980 923 13908 924 13956 925 13794 926 13920 927 13926 928 13965 929 14196 930 14331 931 14253 932 14172 933 14073 934 13935 935 14223 936 14073 937 14253 938 14136 939 14145 940 14154 941 14172 942 14223 943 14271 944 14511 945 14160 946 14304 947 14568 948 14160 949 14358 950 14199 951 14622 952 14430 953 14658 954 14484 955 14376 956 14442 957 14592 958 14862 959 14577 960 14397 961 14694 962 14628 963 14658 964 14628 965 14808 966 14592 967 14820 968 14631 969 14577 970 14646 971 14613 972 14415 973 14934 974 14556 975 14565 976 14748 977 14982 978 15078 979 14826 980 14889 981 14982 982 14973 983 15045 984 14898 985 14898 986 14817 987 14973 988 15132 989 15126 990 15258 991 15243 992 15330 993 15213 994 15204 995 15198 996 15036 997 15483 998 15054 999 15276 1000 15261