1 0 2 1 3 2 4 4 5 7 6 9 7 12 8 14 9 18 10 24 11 26 12 31 13 35 14 37 15 41 16 47 17 53 18 55 19 60 20 64 21 66 22 72 23 76 24 82 25 90 26 94 27 96 28 100 29 102 30 106 31 120 32 123 33 129 34 131 35 141 36 143 37 149 38 155 39 159 40 165 41 171 42 173 43 183 44 185 45 189 46 191 47 203 48 215 49 219 50 221 51 225 52 231 53 233 54 243 55 248 56 254 57 260 58 262 59 268 60 272 61 274 62 284 63 298 64 302 65 304 66 308 67 322 68 328 69 338 70 340 71 344 72 350 73 358 74 364 75 370 76 374 77 380 78 388 79 392 80 400 81 410 82 412 83 422 84 424 85 430 86 434 87 440 88 448 89 452 90 454 91 458 92 470 93 478 94 482 95 490 96 494 97 500 98 511 99 513 100 531 101 537 102 547 103 553 104 559 105 561 106 567 107 577 108 583 109 589 110 591 111 597 112 603 113 607 114 609 115 621 116 631 117 633 118 637 119 643 120 649 121 651 122 663 123 667 124 673 125 681 126 691 127 699 128 709 129 717 130 723 131 729 132 733 133 741 134 747 135 751 136 759 137 763 138 777 139 787 140 799 141 801 142 811 143 813 144 817 145 819 146 829 147 843 148 847 149 849 150 853 151 867 152 871 153 873 154 877 155 897 156 901 157 909 158 919 159 927 160 931 161 937 162 943 163 957 164 961 165 967 166 973 167 981 168 987 169 999 170 1003 171 1009 172 1011 173 1020 174 1022 175 1028 176 1038 177 1040 178 1050 179 1052 180 1058 181 1076 182 1080 183 1082 184 1086 185 1092 186 1098 187 1106 188 1112 189 1118 190 1140 191 1142 192 1152 193 1160 194 1170 195 1176 196 1182 197 1190 198 1202 199 1206 200 1212 201 1218 202 1220 203 1226 204 1238 205 1248 206 1266 207 1268 208 1272 209 1278 210 1280 211 1286 212 1290 213 1292 214 1296 215 1308 216 1310 217 1316 218 1350 219 1356 220 1362 221 1370 222 1388 223 1398 224 1412 225 1416 226 1418 227 1422 228 1428 229 1436 230 1440 231 1442 232 1448 233 1460 234 1470 235 1472 236 1476 237 1478 238 1482 239 1488 240 1500 241 1512 242 1520 243 1532 244 1538 245 1542 246 1548 247 1556 248 1560 249 1568 250 1572 251 1586 252 1590 253 1596 254 1598 255 1602 256 1608 257 1610 258 1616 259 1626 260 1646 261 1652 262 1656 263 1658 264 1682 265 1686 266 1688 267 1698 268 1710 269 1712 270 1722 271 1730 272 1736 273 1742 274 1748 275 1766 276 1772 277 1776 278 1778 279 1790 280 1800 281 1812 282 1820 283 1836 284 1850 285 1856 286 1860 287 1862 288 1866 289 1868 290 1878 291 1890 292 1896 293 1902 294 1920 295 1922 296 1938 297 1940 298 1962 299 1968 300 1976 301 1982 302 1986 303 1988 304 1992 305 2000 306 2006 307 2016 308 2018 309 2028 310 2041 311 2051 312 2057 313 2069 314 2071 315 2075 316 2077 317 2087 318 2099 319 2101 320 2117 321 2119 322 2125 323 2129 324 2131 325 2141 326 2149 327 2167 328 2191 329 2195 330 2201 331 2209 332 2225 333 2227 334 2231 335 2239 336 2255 337 2257 338 2261 339 2269 340 2275 341 2281 342 2285 343 2297 344 2299 345 2321 346 2327 347 2329 348 2335 349 2339 350 2345 351 2359 352 2365 353 2369 354 2371 355 2377 356 2381 357 2387 358 2399 359 2405 360 2411 361 2425 362 2429 363 2435 364 2447 365 2455 366 2461 367 2465 368 2491 369 2509 370 2519 371 2527 372 2531 373 2537 374 2539 375 2545 376 2567 377 2579 378 2581 379 2597 380 2605 381 2609 382 2621 383 2635 384 2645 385 2647 386 2651 387 2659 388 2665 389 2671 390 2675 391 2677 392 2681 393 2687 394 2695 395 2699 396 2701 397 2707 398 2717 399 2719 400 2729 401 2737 402 2741 403 2755 404 2765 405 2777 406 2779 407 2785 408 2789 409 2791 410 2807 411 2821 412 2825 413 2831 414 2839 415 2845 416 2849 417 2867 418 2875 419 2885 420 2891 421 2897 422 2905 423 2915 424 2927 425 2941 426 2945 427 2951 428 2957 429 2959 430 2987 431 2989 432 2999 433 3007 434 3011 435 3025 436 3029 437 3037 438 3049 439 3055 440 3067 441 3071 442 3077 443 3097 444 3107 445 3109 446 3125 447 3151 448 3155 449 3157 450 3169 451 3175 452 3179 453 3191 454 3197 455 3205 456 3209 457 3217 458 3239 459 3241 460 3245 461 3247 462 3259 463 3287 464 3289 465 3295 466 3301 467 3307 468 3311 469 3317 470 3319 471 3331 472 3335 473 3347 474 3349 475 3359 476 3361 477 3377 478 3379 479 3395 480 3401 481 3421 482 3437 483 3445 484 3449 485 3451 486 3455 487 3457 488 3479 489 3487 490 3499 491 3505 492 3515 493 3517 494 3521 495 3527 496 3529 497 3535 498 3545 499 3547 500 3559 501 3569 502 3571 503 3581 504 3595 505 3601 506 3605 507 3611 508 3619 509 3625 510 3631 511 3647 512 3659 513 3661 514 3665 515 3679 516 3685 517 3689 518 3697 519 3707 520 3715 521 3721 522 3727 523 3749 524 3755 525 3757 526 3767 527 3781 528 3785 529 3791 530 3809 531 3811 532 3821 533 3835 534 3839 535 3841 536 3851 537 3865 538 3869 539 3877 540 3895 541 3899 542 3905 543 3907 544 3911 545 3917 546 3919 547 3931 548 3935 549 3955 550 3977 551 3989 552 3991 553 3995 554 4001 555 4007 556 4009 557 4015 558 4037 559 4039 560 4045 561 4061 562 4067 563 4079 564 4081 565 4086 566 4098 567 4114 568 4116 569 4120 570 4126 571 4140 572 4144 573 4146 574 4164 575 4188 576 4198 577 4204 578 4206 579 4216 580 4218 581 4228 582 4230 583 4240 584 4246 585 4248 586 4258 587 4260 588 4270 589 4276 590 4284 591 4314 592 4324 593 4326 594 4336 595 4344 596 4350 597 4360 598 4378 599 4384 600 4396 601 4408 602 4410 603 4428 604 4434 605 4438 606 4444 607 4450 608 4468 609 4470 610 4480 611 4494 612 4500 613 4504 614 4506 615 4510 616 4534 617 4536 618 4548 619 4554 620 4570 621 4578 622 4584 623 4590 624 4608 625 4624 626 4626 627 4630 628 4636 629 4638 630 4644 631 4650 632 4660 633 4666 634 4678 635 4690 636 4708 637 4710 638 4716 639 4720 640 4738 641 4746 642 4770 643 4774 644 4776 645 4780 646 4786 647 4788 648 4800 649 4804 650 4818 651 4848 652 4858 653 4864 654 4876 655 4890 656 4896 657 4906 658 4918 659 4920 660 4924 661 4930 662 4938 663 4944 664 4954 665 4956 666 4960 667 4974 668 4980 669 4986 670 4990 671 4996 672 4998 673 5008 674 5010 675 5026 676 5038 677 5046 678 5064 679 5068 680 5074 681 5086 682 5088 683 5094 684 5100 685 5106 686 5134 687 5140 688 5154 689 5158 690 5166 691 5176 692 5184 693 5196 694 5214 695 5218 696 5220 697 5224 698 5248 699 5260 700 5266 701 5268 702 5284 703 5290 704 5296 705 5310 706 5320 707 5334 708 5338 709 5368 710 5374 711 5380 712 5386 713 5394 714 5400 715 5404 716 5406 717 5418 718 5424 719 5428 720 5430 721 5436 722 5458 723 5464 724 5466 725 5470 726 5488 727 5490 728 5494 729 5506 730 5508 731 5514 732 5518 733 5544 734 5550 735 5556 736 5560 737 5568 738 5578 739 5610 740 5626 741 5628 742 5634 743 5638 744 5640 745 5644 746 5646 747 5656 748 5670 749 5676 750 5680 751 5688 752 5698 753 5704 754 5724 755 5728 756 5730 757 5736 758 5766 759 5770 760 5778 761 5788 762 5794 763 5800 764 5808 765 5814 766 5826 767 5830 768 5836 769 5838 770 5844 771 5848 772 5854 773 5856 774 5866 775 5868 776 5884 777 5890 778 5910 779 5914 780 5926 781 5940 782 5968 783 5974 784 5994 785 5998 786 6016 787 6024 788 6030 789 6034 790 6040 791 6054 792 6060 793 6066 794 6076 795 6078 796 6088 797 6100 798 6108 799 6118 800 6120 801 6130 802 6138 803 6150 804 6160 805 6184 806 6186 807 6190 808 6198 809 6204 810 6208 811 6216 812 6234 813 6244 814 6250 815 6256 816 6258 817 6264 818 6274 819 6286 820 6288 821 6298 822 6304 823 6310 824 6316 825 6324 826 6330 827 6340 828 6346 829 6348 830 6354 831 6360 832 6366 833 6376 834 6384 835 6408 836 6414 837 6436 838 6438 839 6456 840 6460 841 6468 842 6478 843 6508 844 6516 845 6534 846 6538 847 6540 848 6550 849 6556 850 6558 851 6564 852 6568 853 6586 854 6594 855 6606 856 6624 857 6640 858 6646 859 6648 860 6660 861 6666 862 6676 863 6678 864 6688 865 6690 866 6696 867 6706 868 6720 869 6724 870 6748 871 6750 872 6766 873 6768 874 6778 875 6780 876 6790 877 6810 878 6814 879 6816 880 6820 881 6828 882 6844 883 6850 884 6856 885 6858 886 6870 887 6886 888 6894 889 6898 890 6904 891 6934 892 6936 893 6946 894 6948 895 6954 896 6958 897 6964 898 6970 899 6978 900 6984 901 6988 902 7000 903 7006 904 7014 905 7026 906 7030 907 7044 908 7056 909 7066 910 7090 911 7096 912 7108 913 7114 914 7116 915 7138 916 7146 917 7164 918 7174 919 7180 920 7194 921 7198 922 7200 923 7206 924 7216 925 7224 926 7230 927 7234 928 7240 929 7270 930 7284 931 7294 932 7296 933 7308 934 7318 935 7320 936 7336 937 7338 938 7356 939 7380 940 7398 941 7404 942 7420 943 7438 944 7444 945 7446 946 7464 947 7468 948 7474 949 7476 950 7486 951 7494 952 7504 953 7510 954 7516 955 7524 956 7528 957 7534 958 7536 959 7546 960 7548 961 7560 962 7564 963 7570 964 7576 965 7578 966 7590 967 7594 968 7608 969 7626 970 7630 971 7636 972 7656 973 7660 974 7668 975 7674 976 7678 977 7686 978 7690 979 7704 980 7710 981 7714 982 7728 983 7740 984 7744 985 7746 986 7776 987 7780 988 7804 989 7810 990 7816 991 7828 992 7840 993 7854 994 7860 995 7864 996 7866 997 7870 998 7888 999 7894 1000 7906