1 0 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 10 10 11 11 14 12 15 13 16 14 19 15 20 16 24 17 25 18 26 19 29 20 35 21 36 22 39 23 40 24 41 25 45 26 49 27 51 28 54 29 56 30 59 31 61 32 65 33 66 34 69 35 71 36 74 37 79 38 84 39 85 40 90 41 94 42 95 43 101 44 110 45 116 46 120 47 121 48 124 49 126 50 130 51 131 52 134 53 139 54 141 55 145 56 146 57 150 58 156 59 159 60 160 61 165 62 169 63 170 64 171 65 175 66 176 67 180 68 181 69 184 70 195 71 199 72 201 73 204 74 205 75 206 76 209 77 210 78 219 79 221 80 224 81 230 82 231 83 236 84 239 85 240 86 245 87 250 88 256 89 260 90 261 91 264 92 270 93 271 94 275 95 279 96 280 97 284 98 289 99 299 100 300 101 306 102 309 103 314 104 315 105 321 106 325 107 326 108 329 109 335 110 340 111 345 112 349 113 350 114 371 115 375 116 379 117 384 118 386 119 391 120 396 121 399 122 400 123 405 124 406 125 409 126 415 127 420 128 425 129 430 130 435 131 436 132 440 133 441 134 444 135 445 136 449 137 451 138 459 139 461 140 464 141 466 142 470 143 471 144 474 145 490 146 496 147 519 148 521 149 529 150 535 151 536 152 544 153 545 154 556 155 559 156 569 157 570 158 571 159 575 160 576 161 579 162 581 163 584 164 594 165 595 166 609 167 631 168 634 169 636 170 639 171 641 172 644 173 646 174 649 175 654 176 661 177 669 178 674 179 680 180 685 181 686 182 689 183 690 184 695 185 696 186 699 187 700 188 704 189 711 190 714 191 715 192 716 193 739 194 740 195 745 196 750 197 751 198 760 199 764 200 779 201 780 202 781 203 784 204 791 205 799 206 815 207 816 208 819 209 821 210 826 211 841 212 855 213 860 214 861 215 864 216 869 217 875 218 881 219 885 220 890 221 901 222 906 223 909 224 910 225 920 226 921 227 925 228 929 229 930 230 935 231 936 232 946 233 949 234 950 235 951 236 955 237 959 238 960 239 966 240 979 241 981 242 985 243 986 244 989 245 991 246 1001 247 1004 248 1010 249 1011 250 1025 251 1029 252 1031 253 1036 254 1039 255 1051 256 1054 257 1055 258 1060 259 1066 260 1069 261 1070 262 1080 263 1081 264 1091 265 1094 266 1095 267 1096 268 1099 269 1106 270 1111 271 1124 272 1125 273 1129 274 1140 275 1144 276 1146 277 1150 278 1151 279 1155 280 1156 281 1161 282 1171 283 1174 284 1176 285 1179 286 1181 287 1184 288 1185 289 1199 290 1205 291 1210 292 1219 293 1225 294 1241 295 1244 296 1246 297 1251 298 1255 299 1265 300 1274 301 1276 302 1281 303 1285 304 1290 305 1294 306 1299 307 1306 308 1311 309 1314 310 1315 311 1316 312 1320 313 1324 314 1329 315 1340 316 1345 317 1349 318 1350 319 1354 320 1359 321 1361 322 1366 323 1374 324 1376 325 1389 326 1391 327 1394 328 1405 329 1406 330 1410 331 1411 332 1416 333 1419 334 1420 335 1421 336 1430 337 1434 338 1439 339 1440 340 1456 341 1459 342 1460 343 1465 344 1469 345 1489 346 1494 347 1495 348 1499 349 1501 350 1504 351 1515 352 1519 353 1521 354 1524 355 1531 356 1535 357 1541 358 1545 359 1546 360 1550 361 1556 362 1564 363 1566 364 1569 365 1570 366 1576 367 1580 368 1586 369 1589 370 1599 371 1605 372 1614 373 1615 374 1616 375 1629 376 1635 377 1639 378 1640 379 1644 380 1654 381 1660 382 1661 383 1664 384 1674 385 1676 386 1684 387 1686 388 1689 389 1691 390 1700 391 1701 392 1705 393 1709 394 1715 395 1716 396 1736 397 1741 398 1749 399 1756 400 1765 401 1766 402 1771 403 1774 404 1784 405 1790 406 1794 407 1805 408 1811 409 1816 410 1824 411 1831 412 1845 413 1850 414 1855 415 1859 416 1860 417 1869 418 1870 419 1875 420 1876 421 1884 422 1894 423 1899 424 1901 425 1910 426 1915 427 1920 428 1935 429 1940 430 1949 431 1964 432 1966 433 1970 434 1974 435 1980 436 1990 437 2001 438 2006 439 2009 440 2021 441 2026 442 2034 443 2035 444 2050 445 2051 446 2054 447 2055 448 2056 449 2064 450 2065 451 2074 452 2079 453 2080 454 2084 455 2086 456 2091 457 2094 458 2096 459 2106 460 2116 461 2120 462 2125 463 2126 464 2135 465 2136 466 2139 467 2145 468 2151 469 2154 470 2159 471 2161 472 2165 473 2171 474 2174 475 2175 476 2199 477 2201 478 2210 479 2224 480 2239 481 2255 482 2260 483 2261 484 2266 485 2269 486 2271 487 2281 488 2285 489 2286 490 2289 491 2294 492 2304 493 2310 494 2314 495 2315 496 2320 497 2321 498 2326 499 2330 500 2331 501 2336 502 2341 503 2349 504 2351 505 2354 506 2360 507 2375 508 2379 509 2380 510 2381 511 2389 512 2391 513 2404 514 2405 515 2406 516 2420 517 2425 518 2430 519 2454 520 2456 521 2459 522 2460 523 2464 524 2470 525 2481 526 2496 527 2505 528 2516 529 2519 530 2525 531 2534 532 2536 533 2539 534 2541 535 2545 536 2549 537 2550 538 2561 539 2565 540 2570 541 2576 542 2581 543 2585 544 2589 545 2591 546 2594 547 2599 548 2600 549 2604 550 2609 551 2611 552 2619 553 2624 554 2629 555 2635 556 2645 557 2646 558 2654 559 2659 560 2661 561 2664 562 2666 563 2671 564 2676 565 2681 566 2684 567 2691 568 2700 569 2701 570 2705 571 2706 572 2711 573 2719 574 2729 575 2730 576 2731 577 2736 578 2746 579 2754 580 2755 581 2760 582 2765 583 2766 584 2770 585 2771 586 2776 587 2780 588 2785 589 2789 590 2794 591 2799 592 2804 593 2805 594 2815 595 2819 596 2821 597 2824 598 2831 599 2834 600 2836 601 2841 602 2845 603 2849 604 2850 605 2864 606 2871 607 2876 608 2884 609 2889 610 2890 611 2895 612 2896 613 2900 614 2901 615 2905 616 2916 617 2924 618 2925 619 2926 620 2934 621 2935 622 2944 623 2949 624 2951 625 2960 626 2964 627 2965 628 2974 629 2981 630 2986 631 3001 632 3015 633 3016 634 3026 635 3031 636 3035 637 3045 638 3046 639 3049 640 3054 641 3059 642 3071 643 3074 644 3075 645 3094 646 3095 647 3101 648 3106 649 3109 650 3110 651 3119 652 3131 653 3134 654 3136 655 3140 656 3145 657 3156 658 3159 659 3160 660 3171 661 3174 662 3184 663 3191 664 3195 665 3196 666 3201 667 3204 668 3205 669 3211 670 3214 671 3215 672 3220 673 3235 674 3240 675 3241 676 3246 677 3249 678 3254 679 3261 680 3266 681 3274 682 3280 683 3290 684 3291 685 3295 686 3304 687 3306 688 3314 689 3315 690 3321 691 3326 692 3329 693 3334 694 3340 695 3341 696 3350 697 3356 698 3360 699 3365 700 3374 701 3390 702 3391 703 3395 704 3399 705 3419 706 3429 707 3431 708 3436 709 3441 710 3446 711 3459 712 3465 713 3474 714 3480 715 3485 716 3490 717 3491 718 3495 719 3499 720 3501 721 3504 722 3516 723 3519 724 3520 725 3529 726 3530 727 3534 728 3536 729 3539 730 3561 731 3569 732 3571 733 3575 734 3585 735 3605 736 3621 737 3624 738 3644 739 3650 740 3655 741 3660 742 3665 743 3670 744 3675 745 3686 746 3689 747 3691 748 3701 749 3705 750 3709 751 3711 752 3715 753 3716 754 3721 755 3725 756 3730 757 3734 758 3746 759 3751 760 3754 761 3755 762 3756 763 3759 764 3764 765 3774 766 3776 767 3784 768 3785 769 3789 770 3790 771 3794 772 3800 773 3806 774 3819 775 3825 776 3826 777 3835 778 3849 779 3850 780 3851 781 3859 782 3865 783 3870 784 3875 785 3884 786 3885 787 3890 788 3894 789 3900 790 3901 791 3909 792 3910 793 3919 794 3924 795 3935 796 3939 797 3946 798 3951 799 3959 800 3966 801 3981 802 3984 803 3989 804 3994 805 3995 806 4006 807 4011 808 4021 809 4024 810 4026 811 4029 812 4031 813 4034 814 4041 815 4046 816 4049 817 4055 818 4056 819 4065 820 4070 821 4075 822 4079 823 4080 824 4085 825 4086 826 4089 827 4099 828 4114 829 4119 830 4120 831 4121 832 4124 833 4136 834 4140 835 4145 836 4146 837 4154 838 4156 839 4170 840 4171 841 4174 842 4176 843 4180 844 4184 845 4185 846 4189 847 4199 848 4201 849 4206 850 4209 851 4221 852 4225 853 4226 854 4231 855 4241 856 4250 857 4260 858 4265 859 4266 860 4289 861 4294 862 4299 863 4300 864 4301 865 4310 866 4315 867 4330 868 4336 869 4340 870 4345 871 4349 872 4351 873 4359 874 4361 875 4364 876 4366 877 4370 878 4371 879 4374 880 4375 881 4384 882 4404 883 4410 884 4414 885 4435 886 4439 887 4444 888 4445 889 4456 890 4459 891 4465 892 4474 893 4479 894 4485 895 4486 896 4495 897 4496 898 4504 899 4510 900 4511 901 4524 902 4530 903 4531 904 4534 905 4540 906 4554 907 4561 908 4566 909 4585 910 4589 911 4590 912 4600 913 4604 914 4606 915 4609 916 4614 917 4615 918 4616 919 4635 920 4639 921 4644 922 4650 923 4651 924 4661 925 4666 926 4669 927 4689 928 4691 929 4700 930 4704 931 4709 932 4716 933 4719 934 4721 935 4726 936 4734 937 4736 938 4754 939 4759 940 4771 941 4780 942 4784 943 4786 944 4794 945 4795 946 4796 947 4799 948 4801 949 4809 950 4811 951 4825 952 4834 953 4850 954 4859 955 4865 956 4871 957 4876 958 4879 959 4885 960 4886 961 4894 962 4901 963 4904 964 4905 965 4910 966 4920 967 4936 968 4941 969 4944 970 4949 971 4954 972 4956 973 4965 974 4979 975 4990 976 4999 977 5004 978 5009 979 5014 980 5015 981 5016 982 5021 983 5025 984 5030 985 5031 986 5041 987 5044 988 5054 989 5055 990 5056 991 5061 992 5069 993 5071 994 5076 995 5080 996 5085 997 5086 998 5089 999 5105 1000 5109