0 1 1 1 2 1 3 1 4 2 5 2 6 2 7 3 8 4 9 5 10 5 11 6 12 7 13 8 14 9 15 10 16 11 17 12 18 13 19 15 20 15 21 16 22 18 23 19 24 20 25 20 26 21 27 23 28 24 29 25 30 26 31 27 32 29 33 30 34 32 35 33 36 34 37 36 38 37 39 39 40 39 41 41 42 43 43 44 44 46 45 47 46 48 47 50 48 52 49 53 50 53 51 55 52 56 53 58 54 60 55 61 56 62 57 64 58 66 59 68 60 68 61 70 62 72 63 74 64 76 65 76 66 78 67 80 68 82 69 84 70 85 71 86 72 88 73 90 74 92 75 92 76 94 77 96 78 98 79 99 80 100 81 102 82 104 83 106 84 108 85 109 86 111 87 113 88 115 89 117 90 118 91 120 92 122 93 124 94 126 95 127 96 128 97 130 98 132 99 134 100 134 101 136 102 138 103 140 104 143 105 144 106 146 107 148 108 150 109 152 110 153 111 155 112 157 113 159 114 161 115 162 116 164 117 166 118 168 119 170 120 171 121 173 122 175 123 178 124 180 125 179 126 181 127 183 128 185 129 187 130 188 131 190 132 193 133 195 134 197 135 198 136 200 137 202 138 204 139 206 140 208 141 210 142 212 143 214 144 216 145 217 146 220 147 222 148 224 149 226 150 226 151 228 152 231 153 233 154 235 155 236 156 238 157 241 158 243 159 245 160 246 161 248 162 251 163 253 164 255 165 256 166 258 167 261 168 263 169 265 170 266 171 269 172 271 173 273 174 275 175 276 176 278 177 280 178 282 179 285 180 286 181 288 182 290 183 293 184 295 185 296 186 298 187 301 188 303 189 305 190 306 191 309 192 311 193 313 194 316 195 317 196 319 197 322 198 324 199 326 200 326 201 329 202 331 203 333 204 336 205 337 206 339 207 342 208 344 209 346 210 348 211 350 212 352 213 355 214 357 215 358 216 361 217 363 218 365 219 368 220 369 221 371 222 374 223 376 224 378 225 379 226 381 227 383 228 386 229 388 230 389 231 392 232 394 233 396 234 399 235 400 236 403 237 405 238 407 239 410 240 411 241 413 242 416 243 418 244 421 245 422 246 424 247 427 248 429 249 432 250 431 251 433 252 436 253 438 254 441 255 442 256 444 257 447 258 449 259 452 260 453 261 455 262 458 263 460 264 463 265 464 266 467 267 469 268 471 269 474 270 475 271 478 272 480 273 483 274 485 275 486 276 488 277 490 278 493 279 495 280 497 281 499 282 502 283 504 284 507 285 508 286 510 287 513 288 515 289 518 290 519 291 522 292 524 293 527 294 529 295 531 296 533 297 536 298 538 299 541 300 541 301 543 302 546 303 548 304 551 305 552 306 555 307 557 308 560 309 562 310 564 311 566 312 569 313 571 314 574 315 575 316 578 317 580 318 583 319 585 320 587 321 589 322 592 323 594 324 597 325 597 326 600 327 602 328 605 329 607 330 609 331 611 332 614 333 617 334 619 335 621 336 623 337 626 338 628 339 631 340 632 341 635 342 637 343 640 344 642 345 644 346 646 347 649 348 652 349 654 350 655 351 657 352 660 353 662 354 665 355 666 356 669 357 671 358 674 359 677 360 678 361 681 362 683 363 686 364 688 365 690 366 692 367 695 368 698 369 700 370 702 371 704 372 707 373 709 374 712 375 712 376 714 377 717 378 719 379 722 380 723 381 726 382 729 383 731 384 734 385 735 386 738 387 741 388 743 389 746 390 747 391 750 392 753 393 755 394 758 395 759 396 762 397 765 398 767 399 770 400 770 401 773 402 776 403 778 404 781 405 782 406 785 407 788 408 790 409 793 410 794 411 797 412 800 413 802 414 805 415 806 416 809 417 812 418 814 419 817 420 819 421 821 422 824 423 826 424 829 425 830 426 832 427 835 428 838 429 840 430 842 431 844 432 847 433 850 434 852 435 854 436 857 437 859 438 862 439 865 440 866 441 869 442 872 443 874 444 877 445 878 446 881 447 884 448 886 449 889 450 890 451 892 452 895 453 898 454 900 455 902 456 905 457 907 458 910 459 913 460 914 461 917 462 920 463 922 464 925 465 927 466 929 467 932 468 935 469 937 470 939 471 942 472 944 473 947 474 950 475 950 476 953 477 956 478 958 479 961 480 963 481 965 482 968 483 971 484 974 485 975 486 978 487 981 488 983 489 986 490 988 491 990 492 993 493 996 494 998 495 1000 496 1003 497 1005 498 1008 499 1011 500 1011 501 1013 502 1016 503 1019 504 1021 505 1023 506 1026 507 1029 508 1031 509 1034 510 1036 511 1038 512 1041 513 1044 514 1046 515 1048 516 1051 517 1054 518 1056 519 1059 520 1061 521 1063 522 1066 523 1069 524 1072 525 1072 526 1075 527 1078 528 1081 529 1083 530 1085 531 1088 532 1090 533 1093 534 1096 535 1098 536 1100 537 1103 538 1106 539 1109 540 1110 541 1113 542 1116 543 1118 544 1121 545 1123 546 1126 547 1128 548 1131 549 1134 550 1135 551 1137 552 1140 553 1143 554 1146 555 1147 556 1150 557 1153 558 1156 559 1158 560 1160 561 1163 562 1166 563 1168 564 1171 565 1173 566 1176 567 1178 568 1181 569 1184 570 1186 571 1188 572 1191 573 1194 574 1197 575 1197 576 1200 577 1203 578 1206 579 1208 580 1210 581 1213 582 1216 583 1218 584 1221 585 1223 586 1226 587 1229 588 1231 589 1234 590 1236 591 1239 592 1241 593 1244 594 1247 595 1249 596 1251 597 1254 598 1257 599 1260 600 1261 601 1263 602 1266 603 1269 604 1272 605 1274 606 1276 607 1279 608 1282 609 1285 610 1286 611 1289 612 1292 613 1295 614 1298 615 1299 616 1302 617 1305 618 1308 619 1311 620 1312 621 1315 622 1318 623 1321 624 1323 625 1322 626 1325 627 1328 628 1331 629 1333 630 1335 631 1338 632 1341 633 1344 634 1346 635 1348 636 1351 637 1354 638 1357 639 1360 640 1361 641 1364 642 1367 643 1370 644 1373 645 1374 646 1377 647 1380 648 1383 649 1386 650 1386 651 1389 652 1392 653 1395 654 1398 655 1399 656 1402 657 1405 658 1408 659 1411 660 1413 661 1415 662 1418 663 1421 664 1424 665 1426 666 1429 667 1431 668 1434 669 1437 670 1439 671 1442 672 1444 673 1447 674 1450 675 1451 676 1454 677 1457 678 1459 679 1462 680 1464 681 1467 682 1470 683 1473 684 1475 685 1477 686 1480 687 1483 688 1486 689 1489 690 1490 691 1493 692 1496 693 1499 694 1502 695 1504 696 1507 697 1509 698 1512 699 1515 700 1516 701 1519 702 1522 703 1524 704 1527 705 1529 706 1532 707 1535 708 1538 709 1541 710 1542 711 1545 712 1548 713 1551 714 1554 715 1556 716 1558 717 1561 718 1564 719 1567 720 1569 721 1572 722 1575 723 1577 724 1580 725 1581 726 1584 727 1587 728 1590 729 1593 730 1595 731 1597 732 1600 733 1603 734 1606 735 1608 736 1611 737 1614 738 1616 739 1619 740 1621 741 1624 742 1627 743 1630 744 1633 745 1635 746 1637 747 1640 748 1643 749 1646 750 1646 751 1649 752 1652 753 1655 754 1657 755 1659 756 1662 757 1665 758 1668 759 1671 760 1673 761 1676 762 1678 763 1681 764 1684 765 1686 766 1689 767 1692 768 1695 769 1698 770 1700 771 1702 772 1705 773 1708 774 1711 775 1712 776 1715 777 1718 778 1721 779 1724 780 1725 781 1728 782 1731 783 1734 784 1737 785 1739 786 1742 787 1745 788 1748 789 1750 790 1752 791 1755 792 1758 793 1761 794 1764 795 1766 796 1769 797 1772 798 1775 799 1777 800 1778 801 1781 802 1784 803 1787 804 1790 805 1792 806 1795 807 1798 808 1801 809 1804 810 1805 811 1808 812 1811 813 1814 814 1817 815 1819 816 1822 817 1825 818 1828 819 1831 820 1833 821 1835 822 1838 823 1841 824 1844 825 1845 826 1848 827 1851 828 1854 829 1857 830 1859 831 1862 832 1865 833 1867 834 1870 835 1872 836 1875 837 1878 838 1881 839 1884 840 1886 841 1889 842 1892 843 1895 844 1898 845 1900 846 1903 847 1905 848 1908 849 1911 850 1912 851 1915 852 1918 853 1921 854 1924 855 1926 856 1929 857 1932 858 1935 859 1938 860 1940 861 1942 862 1945 863 1948 864 1951 865 1953 866 1956 867 1959 868 1962 869 1965 870 1967 871 1970 872 1973 873 1976 874 1979 875 1979 876 1982 877 1985 878 1987 879 1990 880 1992 881 1995 882 1998 883 2001 884 2004 885 2006 886 2009 887 2012 888 2015 889 2018 890 2020 891 2023 892 2026 893 2029 894 2032 895 2034 896 2037 897 2039 898 2042 899 2045 900 2046 901 2049 902 2052 903 2055 904 2058 905 2060 906 2063 907 2066 908 2069 909 2072 910 2074 911 2077 912 2080 913 2083 914 2086 915 2088 916 2091 917 2094 918 2097 919 2100 920 2102 921 2104 922 2107 923 2110 924 2113 925 2114 926 2117 927 2120 928 2123 929 2126 930 2128 931 2131 932 2134 933 2137 934 2140 935 2142 936 2145 937 2148 938 2151 939 2154 940 2156 941 2159 942 2162 943 2165 944 2168 945 2170 946 2173 947 2176 948 2179 949 2182 950 2183 951 2186 952 2189 953 2192 954 2195 955 2197 956 2200 957 2203 958 2205 959 2208 960 2210 961 2213 962 2216 963 2219 964 2222 965 2224 966 2227 967 2230 968 2233 969 2236 970 2238 971 2241 972 2244 973 2247 974 2250 975 2251 976 2254 977 2257 978 2260 979 2263 980 2265 981 2268 982 2271 983 2274 984 2277 985 2279 986 2282 987 2285 988 2288 989 2291 990 2293 991 2296 992 2299 993 2302 994 2305 995 2307 996 2310 997 2313 998 2316 999 2319 1000 2319