1 0 2 0 3 1 4 2 5 6 6 9 7 11 8 13 9 16 10 25 11 21 12 33 13 29 14 31 15 40 16 49 17 54 18 57 19 61 20 62 21 63 22 74 23 78 24 83 25 87 26 97 27 96 28 102 29 97 30 107 31 115 32 126 33 131 34 133 35 145 36 140 37 147 38 157 39 160 40 169 41 174 42 177 43 170 44 183 45 193 46 194 47 205 48 211 49 222 50 217 51 227 52 230 53 227 54 242 55 251 56 256 57 265 58 263 59 267 60 275 61 274 62 289 63 295 64 292 65 293 66 313 67 323 68 317 69 342 70 345 71 347 72 350 73 359 74 369 75 373 76 376 77 385 78 387 79 395 80 367 81 414 82 417 83 419 84 423 85 419 86 438 87 443 88 431 89 457 90 458 91 462 92 464 93 482 94 485 95 487 96 496 97 505 98 515 99 517 100 537 101 541 102 553 103 558 104 563 105 563 106 567 107 582 108 587 109 590 110 587 111 602 112 609 113 611 114 613 115 619 116 635 117 625 118 640 119 649 120 654 121 657 122 663 123 673 124 668 125 682 126 697 127 705 128 706 129 715 130 721 131 730 132 736 133 746 134 753 135 749 136 747 137 769 138 781 139 793 140 803 141 803 142 817 143 818 144 822 145 825 146 826 147 849 148 851 149 853 150 856 151 873 152 875 153 877 154 880 155 901 156 891 157 907 158 923 159 927 160 937 161 942 162 947 163 960 164 962 165 971 166 976 167 983 168 983 169 987 170 1007 171 1014 172 1001 173 1015 174 1023 175 1034 176 1043 177 1039 178 1057 179 1058 180 1057 181 1082 182 1085 183 1083 184 1091 185 1095 186 1105 187 1113 188 1117 189 1107 190 1132 191 1143 192 1155 193 1165 194 1167 195 1182 196 1187 197 1179 198 1209 199 1211 200 1216 201 1225 202 1226 203 1233 204 1235 205 1254 206 1273 207 1274 208 1278 209 1277 210 1285 211 1277 212 1297 213 1295 214 1302 215 1304 216 1295 217 1315 218 1355 219 1360 220 1369 221 1377 222 1381 223 1403 224 1411 225 1422 226 1417 227 1427 228 1430 229 1442 230 1446 231 1449 232 1450 233 1460 234 1475 235 1477 236 1480 237 1461 238 1489 239 1494 240 1498 241 1518 242 1525 243 1536 244 1545 245 1547 246 1538 247 1562 248 1566 249 1571 250 1576 251 1575 252 1595 253 1600 254 1595 255 1607 256 1614 257 1617 258 1618 259 1633 260 1635 261 1658 262 1662 263 1665 264 1689 265 1691 266 1690 267 1703 268 1715 269 1714 270 1729 271 1737 272 1741 273 1739 274 1751 275 1767 276 1771 277 1782 278 1777 279 1779 280 1802 281 1816 282 1819 283 1840 284 1857 285 1861 286 1855 287 1853 288 1873 289 1871 290 1883 291 1897 292 1902 293 1907 294 1926 295 1923 296 1945 297 1946 298 1969 299 1974 300 1981 301 1983 302 1993 303 1991 304 1995 305 2003 306 2007 307 2022 308 2025 309 2030 310 2049 311 2056 312 2065 313 2075 314 2077 315 2080 316 2075 317 2094 318 2102 319 2103 320 2123 321 2125 322 2117 323 2137 324 2131 325 2147 326 2115 327 2167 328 2191 329 2200 330 2209 331 2217 332 2233 333 2234 334 2238 335 2239 336 2262 337 2265 338 2267 339 2267 340 2261 341 2289 342 2287 343 2305 344 2306 345 2329 346 2334 347 2327 348 2338 349 2335 350 2353 351 2365 352 2367 353 2375 354 2365 355 2385 356 2387 357 2386 358 2402 359 2411 360 2416 361 2433 362 2429 363 2440 364 2454 365 2461 366 2463 367 2473 368 2498 369 2487 370 2526 371 2533 372 2536 373 2545 374 2543 375 2553 376 2574 377 2582 378 2579 379 2603 380 2607 381 2617 382 2627 383 2642 384 2651 385 2653 386 2656 387 2659 388 2673 389 2677 390 2679 391 2651 392 2689 393 2694 394 2701 395 2702 396 2703 397 2714 398 2723 399 2723 400 2737 401 2737 402 2747 403 2755 404 2771 405 2785 406 2778 407 2793 408 2795 409 2797 410 2814 411 2823 412 2833 413 2837 414 2845 415 2835 416 2857 417 2870 418 2880 419 2891 420 2896 421 2905 422 2907 423 2920 424 2934 425 2927 426 2953 427 2958 428 2963 429 2956 430 2980 431 2973 432 3006 433 3013 434 3016 435 3033 436 3035 437 3027 438 3049 439 3061 440 3071 441 3078 442 3083 443 3097 444 3110 445 3107 446 3131 447 3154 448 3160 449 3155 450 3167 451 3181 452 3175 453 3198 454 3203 455 3207 456 3201 457 3217 458 3242 459 3249 460 3251 461 3251 462 3263 463 3294 464 3289 465 3301 466 3293 467 3311 468 3318 469 3323 470 3323 471 3327 472 3342 473 3346 474 3317 475 3366 476 3363 477 3383 478 3383 479 3400 480 3409 481 3423 482 3443 483 3443 484 3457 485 3451 486 3462 487 3465 488 3486 489 3493 490 3502 491 3513 492 3520 493 3495 494 3529 495 3534 496 3527 497 3541 498 3553 499 3554 500 3565 501 3577 502 3578 503 3587 504 3591 505 3609 506 3611 507 3616 508 3606 509 3633 510 3637 511 3654 512 3656 513 3663 514 3673 515 3685 516 3687 517 3697 518 3705 519 3710 520 3722 521 3729 522 3727 523 3755 524 3760 525 3755 526 3774 527 3783 528 3793 529 3798 530 3815 531 3811 532 3827 533 3840 534 3845 535 3849 536 3856 537 3873 538 3855 539 3867 540 3901 541 3896 542 3913 543 3914 544 3918 545 3923 546 3925 547 3931 548 3942 549 3959 550 3985 551 3995 552 3997 553 4000 554 4009 555 4013 556 4017 557 4018 558 4043 559 4036 560 4047 561 4067 562 4066 563 4086 564 4089 565 4093 566 4097 567 4120 568 4103 569 4129 570 4134 571 4143 572 4153 573 4154 574 4167 575 4179 576 4202 577 4211 578 4213 579 4225 580 4226 581 4235 582 4237 583 4249 584 4254 585 4257 586 4261 587 4263 588 4278 589 4283 590 4287 591 4322 592 4331 593 4324 594 4345 595 4353 596 4357 597 4369 598 4375 599 4393 600 4403 601 4415 602 4413 603 4399 604 4442 605 4446 606 4451 607 4456 608 4475 609 4477 610 4489 611 4501 612 4499 613 4513 614 4507 615 4515 616 4542 617 4537 618 4539 619 4557 620 4576 621 4578 622 4587 623 4597 624 4617 625 4633 626 4634 627 4635 628 4643 629 4643 630 4627 631 4651 632 4667 633 4666 634 4686 635 4696 636 4709 637 4717 638 4695 639 4723 640 4729 641 4751 642 4775 643 4782 644 4785 645 4787 646 4790 647 4787 648 4809 649 4811 650 4826 651 4839 652 4857 653 4873 654 4883 655 4898 656 4897 657 4904 658 4922 659 4929 660 4931 661 4934 662 4943 663 4953 664 4960 665 4947 666 4969 667 4981 668 4983 669 4987 670 4998 671 5003 672 5005 673 5015 674 5018 675 5026 676 5046 677 5053 678 5073 679 5075 680 5080 681 5094 682 5089 683 5101 684 5075 685 5114 686 5142 687 5143 688 5150 689 5165 690 5173 691 5185 692 5183 693 5175 694 5221 695 5222 696 5213 697 5231 698 5257 699 5267 700 5269 701 5267 702 5291 703 5296 704 5305 705 5308 706 5329 707 5338 708 5338 709 5375 710 5382 711 5387 712 5390 713 5402 714 5403 715 5411 716 5411 717 5426 718 5427 719 5435 720 5437 721 5435 722 5461 723 5473 724 5474 725 5478 726 5497 727 5491 728 5502 729 5504 730 5499 731 5520 732 5516 733 5553 734 5557 735 5543 736 5569 737 5569 738 5578 739 5616 740 5630 741 5613 742 5642 743 5646 744 5643 745 5651 746 5653 747 5663 748 5677 749 5667 750 5689 751 5697 752 5689 753 5713 754 5727 755 5737 756 5731 757 5745 758 5773 759 5774 760 5783 761 5795 762 5800 763 5809 764 5809 765 5821 766 5831 767 5837 768 5843 769 5845 770 5843 771 5855 772 5859 773 5865 774 5866 775 5819 776 5891 777 5896 778 5917 779 5920 780 5934 781 5939 782 5975 783 5982 784 5995 785 6005 786 6025 787 6027 788 6032 789 6040 790 6049 791 6061 792 6053 793 6055 794 6083 795 6073 796 6097 797 6107 798 6107 799 6126 800 6123 801 6136 802 6141 803 6154 804 6169 805 6193 806 6194 807 6198 808 6205 809 6207 810 6215 811 6225 812 6240 813 6251 814 6256 815 6265 816 6243 817 6273 818 6278 819 6294 820 6281 821 6302 822 6313 823 6318 824 6323 825 6317 826 6338 827 6347 828 6344 829 6323 830 6362 831 6369 832 6373 833 6385 834 6393 835 6409 836 6418 837 6443 838 6442 839 6465 840 6467 841 6467 842 6486 843 6509 844 6515 845 6541 846 6532 847 6533 848 6548 849 6563 850 6561 851 6567 852 6553 853 6584 854 6602 855 6613 856 6633 857 6649 858 6654 859 6649 860 6663 861 6667 862 6683 863 6685 864 6697 865 6696 866 6705 867 6706 868 6729 869 6731 870 6755 871 6757 872 6774 873 6777 874 6781 875 6773 876 6798 877 6818 878 6822 879 6825 880 6827 881 6797 882 6851 883 6856 884 6865 885 6859 886 6877 887 6894 888 6901 889 6902 890 6913 891 6942 892 6945 893 6949 894 6935 895 6949 896 6965 897 6971 898 6976 899 6983 900 6987 901 6995 902 7009 903 7014 904 7021 905 7034 906 7037 907 7047 908 7065 909 7070 910 7096 911 7105 912 7115 913 7120 914 7115 915 7141 916 7154 917 7157 918 7182 919 7187 920 7202 921 7206 922 7203 923 7213 924 7225 925 7233 926 7237 927 7240 928 7249 929 7278 930 7287 931 7302 932 7297 933 7307 934 7325 935 7321 936 7345 937 7340 938 7355 939 7383 940 7405 941 7407 942 7427 943 7445 944 7451 945 7453 946 7473 947 7469 948 7479 949 7475 950 7494 951 7501 952 7513 953 7518 954 7523 955 7523 956 7537 957 7542 958 7545 959 7544 960 7535 961 7569 962 7571 963 7576 964 7585 965 7583 966 7597 967 7600 968 7617 969 7627 970 7638 971 7643 972 7665 973 7667 974 7647 975 7679 976 7686 977 7691 978 7696 979 7713 980 7714 981 7720 982 7727 983 7733 984 7753 985 7754 986 7785 987 7787 988 7811 989 7816 990 7825 991 7817 992 7849 993 7858 994 7863 995 7873 996 7874 997 7878 998 7897 999 7902 1000 7910 1001 7917