0 2 1 2 2 5 3 7 4 11 5 17 6 23 7 29 8 37 9 47 10 59 11 67 12 79 13 97 14 107 15 127 16 137 17 157 18 173 19 191 20 211 21 233 22 257 23 277 24 307 25 331 26 353 27 379 28 409 29 439 30 467 31 499 32 541 33 563 34 599 35 631 36 673 37 709 38 743 39 787 40 821 41 863 42 907 43 947 44 991 45 1039 46 1087 47 1129 48 1181 49 1229 50 1277 51 1327 52 1381 53 1433 54 1487 55 1543 56 1597 57 1657 58 1721 59 1777 60 1831 61 1901 62 1973 63 2017 64 2081 65 2153 66 2213 67 2281 68 2347 69 2417 70 2503 71 2557 72 2633 73 2707 74 2777 75 2851 76 2927 77 3011 78 3083 79 3163 80 3251 81 3323 82 3407 83 3491 84 3571 85 3659 86 3761 87 3833 88 3917 89 4007 90 4099 91 4201 92 4283 93 4373 94 4481 95 4561 96 4657 97 4759 98 4861 99 4951 100 5051 101 5153 102 5261 103 5381 104 5471 105 5569 106 5683 107 5779 108 5897 109 6007 110 6113 111 6217 112 6329 113 6449 114 6563 115 6673 116 6791 117 6907 118 7027 119 7151 120 7283 121 7393 122 7507 123 7639 124 7753 125 7877 126 8009 127 8147 128 8263 129 8387 130 8521 131 8647 132 8779 133 8923 134 9049 135 9181 136 9319 137 9461 138 9601 139 9733 140 9871 141 10037 142 10159 143 10301 144 10453 145 10589 146 10733 147 10883 148 11027 149 11177 150 11329 151 11483 152 11633 153 11783 154 11939 155 12097 156 12251 157 12409 158 12569 159 12721 160 12889 161 13043 162 13217 163 13367 164 13537 165 13697 166 13873 167 14029 168 14197 169 14369 170 14537 171 14713 172 14879 173 15053 174 15227 175 15401 176 15581 177 15761 178 15937 179 16111 180 16301 181 16477 182 16657 183 16843 184 17021 185 17207 186 17393 187 17579 188 17783 189 17957 190 18149 191 18341 192 18539 193 18731 194 18917 195 19121 196 19309 197 19507 198 19709 199 19913 200 20101 201 20323 202 20507 203 20707 204 20921 205 21121 206 21323 207 21529 208 21737 209 21961 210 22157 211 22367 212 22613 213 22807 214 23011 215 23227 216 23447 217 23663 218 23873 219 24091 220 24317 221 24533 222 24763 223 24977 224 25219 225 25439 226 25657 227 25889 228 26107 229 26339 230 26573 231 26801 232 27031 233 27271 234 27509 235 27733 236 27967 237 28211 238 28447 239 28687 240 28921 241 29167 242 29411 243 29663 244 29917 245 30137 246 30389 247 30631 248 30881 249 31139 250 31379 251 31627 252 31883 253 32141 254 32401 255 32647 256 32909 257 33161 258 33413 259 33679 260 33931 261 34211 262 34457 263 34721 264 34981 265 35251 266 35521 267 35797 268 36061 269 36319 270 36587 271 36857 272 37139 273 37409 274 37691 275 37951 276 38231 277 38543 278 38783 279 39079 280 39341 281 39623 282 39929 283 40189 284 40471 285 40759 286 41047 287 41333 288 41617 289 41911 290 42197 291 42487 292 42787 293 43093 294 43391 295 43661 296 43961 297 44257 298 44563 299 44851 300 45161 301 45481 302 45757 303 46061 304 46381 305 46679 306 46993 307 47279 308 47591 309 47903 310 48221 311 48523 312 48847 313 49157 314 49459 315 49783 316 50087 317 50411 318 50723 319 51043 320 51361 321 51683 322 52009 323 52361 324 52667 325 52981 326 53309 327 53629 328 53959 329 54287 330 54617 331 54949 332 55291 333 55619 334 55949 335 56299 336 56629 337 56957 338 57301 339 57637 340 57973 341 58313 342 58657 343 58997 344 59341 345 59693 346 60037 347 60383 348 60727 349 61091 350 61441 351 61781 352 62129 353 62483 354 62851 355 63197 356 63559 357 63907 358 64271 359 64621 360 64997 361 65353 362 65707 363 66067 364 66431 365 66797 366 67169 367 67531 368 67901 369 68279 370 68639 371 69011 372 69379 373 69761 374 70139 375 70501 376 70877 377 71257 378 71633 379 72019 380 72421 381 72797 382 73181 383 73547 384 73939 385 74311 386 74699 387 75079 388 75479 389 75869 390 76249 391 76649 392 77029 393 77431 394 77839 395 78229 396 78607 397 79031 398 79411 399 79801 400 80207 401 80603 402 81013 403 81409 404 81817 405 82217 406 82633 407 83047 408 83437 409 83857 410 84263 411 84673 412 85081 413 85513 414 85909 415 86323 416 86743 417 87179 418 87583 419 87991 420 88411 421 88843 422 89261 423 89681 424 90107 425 90527 426 90971 427 91381 428 91807 429 92237 430 92669 431 93097 432 93529 433 93967 434 94397 435 94837 436 95267 437 95707 438 96149 439 96581 440 97021 441 97463 442 97919 443 98347 444 98801 445 99241 446 99689 447 100129 448 100591 449 101027 450 101477 451 101929 452 102397 453 102841 454 103289 455 103769 456 104207 457 104659 458 105137 459 105601 460 106031 461 106501 462 106957 463 107441 464 107881 465 108347 466 108821 467 109279 468 109751 469 110221 470 110711 471 111187 472 111637 473 112103 474 112577 475 113051 476 113537 477 114013 478 114487 479 114967 480 115459 481 115931 482 116411 483 116903 484 117371 485 117877 486 118343 487 118831 488 119321 489 119809 490 120299 491 120811 492 121283 493 121787 494 122267 495 122761 496 123259 497 123757 498 124277 499 124753 500 125261 501 125753 502 126257 503 126757 504 127261 505 127781 506 128273 507 128813 508 129287 509 129803 510 130307 511 130817 512 131357 513 131849 514 132361 515 132887 516 133387 517 133919 518 134437 519 134947 520 135461 521 136013 522 136511 523 137029 524 137567 525 138077 526 138617 527 139133 528 139661 529 140191 530 140717 531 141257 532 141793 533 142319 534 142867 535 143387 536 143947 537 144461 538 145007 539 145531 540 146077 541 146617 542 147163 543 147703 544 148243 545 148793 546 149333 547 149893 548 150427 549 150979 550 151531 551 152077 552 152629 553 153191 554 153739 555 154291 556 154849 557 155413 558 156007 559 156521 560 157081 561 157649 562 158209 563 158771 564 159337 565 159899 566 160481 567 161033 568 161599 569 162209 570 162739 571 163307 572 163883 573 164471 574 165037 575 165601 576 166183 577 166781 578 167339 579 167911 580 168491 581 169079 582 169657 583 170239 584 170827 585 171427 586 172001 587 172583 588 173177 589 173773 590 174347 591 174943 592 175543 593 176123 594 176741 595 177319 596 177907 597 178513 598 179107 599 179717 600 180307 601 180907 602 181513 603 182107 604 182711 605 183317 606 183943 607 184553 608 185137 609 185747 610 186377 611 187003 612 187597 613 188197 614 188827 615 189421 616 190051 617 190657 618 191281 619 191899 620 192529 621 193133 622 193757 623 194377 624 195023 625 195659 626 196271 627 196879 628 197507 629 198139 630 198769 631 199399 632 200029 633 200671 634 201307 635 201937 636 202567 637 203207 638 203843 639 204481 640 205129 641 205763 642 206407 643 207061 644 207709 645 208337 646 208991 647 209639 648 210277 649 210929 650 211583 651 212227 652 212881 653 213533 654 214189 655 214849 656 215497 657 216157 658 216829 659 217489 660 218131 661 218797 662 219463 663 220123 664 220783 665 221447 666 222113 667 222779 668 223463 669 224129 670 224797 671 225457 672 226129 673 226813 674 227489 675 228181 676 228829 677 229507 678 230189 679 230861 680 231547 681 232259 682 232907 683 233591 684 234271 685 234959 686 235661 687 236329 688 237019 689 237707 690 238397 691 239087 692 239779 693 240473 694 241169 695 241861 696 242591 697 243259 698 243953 699 244667 700 245383 701 246073 702 246769 703 247463 704 248161 705 248867 706 249583 707 250279 708 250993 709 251701 710 252409 711 253133 712 253853 713 254557 714 255259 715 255971 716 256687 717 257407 718 258127 719 258847 720 259577 721 260317 722 261011 723 261739 724 262459 725 263183 726 263909 727 264631 728 265381 729 266089 730 266821 731 267551 732 268283 733 269023 734 269749 735 270493 736 271217 737 271967 738 272693 739 273433 740 274171 741 274931 742 275657 743 276401 744 277157 745 277889 746 278639 747 279397 748 280129 749 280879 750 281627 751 282377 752 283133 753 283909 754 284651 755 285421 756 286163 757 286927 758 287669 759 288427 760 289181 761 289951 762 290707 763 291481 764 292231 765 293021 766 293767 767 294529 768 295313 769 296071 770 296843 771 297607 772 298399 773 299171 774 299933 775 300719 776 301487 777 302261 778 303049 779 303817 780 304597 781 305377 782 306157 783 306941 784 307733 785 308507 786 309293 787 310081 788 310867 789 311659 790 312451 791 313241 792 314059 793 314827 794 315617 795 316423 796 317209 797 318007 798 318809 799 319601 800 320401 801 321203 802 322009 803 322807 804 323623 805 324419 806 325229 807 326057 808 326863 809 327647 810 328481 811 329267 812 330097 813 330899 814 331711 815 332561 816 333337 817 334157 818 334973 819 335807 820 336613 821 337453 822 338263 823 339091 824 339907 825 340757 826 341557 827 342379 828 343219 829 344039 830 344873 831 345701 832 346529 833 347401 834 348209 835 349039 836 349871 837 350711 838 351551 839 352381 840 353237 841 354073 842 354911 843 355753 844 356591 845 357437 846 358289 847 359129 848 359981 849 360827 850 361679 851 362561 852 363379 853 364241 854 365089 855 365941 856 366811 857 367663 858 368513 859 369407 860 370241 861 371099 862 371957 863 372817 864 373693 865 374557 866 375413 867 376283 868 377147 869 378019 870 378893 871 379777 872 380629 873 381509 874 382391 875 383261 876 384133 877 385013 878 385897 879 386777 880 387641 881 388529 882 389437 883 390289 884 391177 885 392059 886 392957 887 393847 888 394717 889 395611 890 396509 891 397427 892 398287 893 399173 894 400067 895 400963 896 401861 897 402757 898 403661 899 404557 900 405473 901 406361 902 407257 903 408169 904 409063 905 409967 906 410899 907 411779 908 412717 909 413597 910 414521 911 415427 912 416333 913 417251 914 418157 915 419087 916 419999 917 420919 918 421831 919 422749 920 423667 921 424597 922 425519 923 426427 924 427351 925 428297 926 429211 927 430139 928 431063 929 431993 930 432923 931 433847 932 434783 933 435731 934 436649 935 437587 936 438517 937 439459 938 440393 939 441349 940 442271 941 443221 942 444167 943 445097 944 446041 945 447001 946 447943 947 448879 948 449833 949 450787 950 451747 951 452687 952 453631 953 454603 954 455537 955 456499 956 457459 957 458407 958 459373 959 460337 960 461297 961 462263 962 463207 963 464171 964 465133 965 466121 966 467063 967 468029 968 469009 969 469969 970 470941 971 471907 972 472883 973 473857 974 474839 975 475807 976 476783 977 477767 978 478739 979 479749 980 480707 981 481673 982 482659 983 483643 984 484621 985 485609 986 486601 987 487589 988 488567 989 489557 990 490549 991 491537 992 492551 993 493523 994 494519 995 495511 996 496511 997 497507 998 498521 999 499507 1000 500501