0 1 1 3 2 5 3 7 4 9 5 12 6 15 7 17 8 19 9 21 10 24 11 27 12 29 13 31 14 33 15 36 16 39 17 41 18 43 19 45 20 48 21 51 22 53 23 55 24 57 25 60 26 63 27 65 28 67 29 69 30 72 31 75 32 77 33 79 34 81 35 84 36 87 37 89 38 91 39 93 40 96 41 99 42 101 43 103 44 105 45 108 46 111 47 113 48 115 49 117 50 120 51 123 52 125 53 127 54 129 55 132 56 135 57 137 58 139 59 141 60 144 61 147 62 149 63 151 64 153 65 156 66 159 67 161 68 163 69 165 70 168 71 171 72 173 73 175 74 177 75 180 76 183 77 185 78 187 79 189 80 192 81 195 82 197 83 199 84 201 85 204 86 207 87 209 88 211 89 213 90 216 91 219 92 221 93 223 94 225 95 228 96 231 97 233 98 235 99 237 100 240 101 243 102 245 103 247 104 249 105 252 106 255 107 257 108 259 109 261 110 264 111 267 112 269 113 271 114 273 115 276 116 279 117 281 118 283 119 285 120 288 121 291 122 293 123 295 124 297 125 300 126 303 127 305 128 307 129 309 130 312 131 315 132 317 133 319 134 321 135 324 136 327 137 329 138 331 139 333 140 336 141 339 142 341 143 343 144 345 145 348 146 351 147 353 148 355 149 357 150 360 151 363 152 365 153 367 154 369 155 372 156 375 157 377 158 379 159 381 160 384 161 387 162 389 163 391 164 393 165 396 166 399 167 401 168 403 169 405 170 408 171 411 172 413 173 415 174 417 175 420 176 423 177 425 178 427 179 429 180 432 181 435 182 437 183 439 184 441 185 444 186 447 187 449 188 451 189 453 190 456 191 459 192 461 193 463 194 465 195 468 196 471 197 473 198 475 199 477 200 480 201 483 202 485 203 487 204 489 205 492 206 495 207 497 208 499 209 501 210 504 211 507 212 509 213 511 214 513 215 516 216 519 217 521 218 523 219 525 220 528 221 531 222 533 223 535 224 537 225 540 226 543 227 545 228 547 229 549 230 552 231 555 232 557 233 559 234 561 235 564 236 567 237 569 238 571 239 573 240 576 241 579 242 581 243 583 244 585 245 588 246 591 247 593 248 595 249 597 250 600 251 603 252 605 253 607 254 609 255 612 256 615 257 617 258 619 259 621 260 624 261 627 262 629 263 631 264 633 265 636 266 639 267 641 268 643 269 645 270 648 271 651 272 653 273 655 274 657 275 660 276 663 277 665 278 667 279 669 280 672 281 675 282 677 283 679 284 681 285 684 286 687 287 689 288 691 289 693 290 696 291 699 292 701 293 703 294 705 295 708 296 711 297 713 298 715 299 717 300 720 301 723 302 725 303 727 304 729 305 732 306 735 307 737 308 739 309 741 310 744 311 747 312 749 313 751 314 753 315 756 316 759 317 761 318 763 319 765 320 768 321 771 322 773 323 775 324 777 325 780 326 783 327 785 328 787 329 789 330 792 331 795 332 797 333 799 334 801 335 804 336 807 337 809 338 811 339 813 340 816 341 819 342 821 343 823 344 825 345 828 346 831 347 833 348 835 349 837 350 840 351 843 352 845 353 847 354 849 355 852 356 855 357 857 358 859 359 861 360 864 361 867 362 869 363 871 364 873 365 876 366 879 367 881 368 883 369 885 370 888 371 891 372 893 373 895 374 897 375 900 376 903 377 905 378 907 379 909 380 912 381 915 382 917 383 919 384 921 385 924 386 927 387 929 388 931 389 933 390 936 391 939 392 941 393 943 394 945 395 948 396 951 397 953 398 955 399 957 400 960 401 963 402 965 403 967 404 969 405 972 406 975 407 977 408 979 409 981 410 984 411 987 412 989 413 991 414 993 415 996 416 999 417 1001 418 1003 419 1005 420 1008 421 1011 422 1013 423 1015 424 1017 425 1020 426 1023 427 1025 428 1027 429 1029 430 1032 431 1035 432 1037 433 1039 434 1041 435 1044 436 1047 437 1049 438 1051 439 1053 440 1056 441 1059 442 1061 443 1063 444 1065 445 1068 446 1071 447 1073 448 1075 449 1077 450 1080 451 1083 452 1085 453 1087 454 1089 455 1092 456 1095 457 1097 458 1099 459 1101 460 1104 461 1107 462 1109 463 1111 464 1113 465 1116 466 1119 467 1121 468 1123 469 1125 470 1128 471 1131 472 1133 473 1135 474 1137 475 1140 476 1143 477 1145 478 1147 479 1149 480 1152 481 1155 482 1157 483 1159 484 1161 485 1164 486 1167 487 1169 488 1171 489 1173 490 1176 491 1179 492 1181 493 1183 494 1185 495 1188 496 1191 497 1193 498 1195 499 1197 500 1200 501 1203 502 1205 503 1207 504 1209 505 1212 506 1215 507 1217 508 1219 509 1221 510 1224 511 1227 512 1229 513 1231 514 1233 515 1236 516 1239 517 1241 518 1243 519 1245 520 1248 521 1251 522 1253 523 1255 524 1257 525 1260 526 1263 527 1265 528 1267 529 1269 530 1272 531 1275 532 1277 533 1279 534 1281 535 1284 536 1287 537 1289 538 1291 539 1293 540 1296 541 1299 542 1301 543 1303 544 1305 545 1308 546 1311 547 1313 548 1315 549 1317 550 1320 551 1323 552 1325 553 1327 554 1329 555 1332 556 1335 557 1337 558 1339 559 1341 560 1344 561 1347 562 1349 563 1351 564 1353 565 1356 566 1359 567 1361 568 1363 569 1365 570 1368 571 1371 572 1373 573 1375 574 1377 575 1380 576 1383 577 1385 578 1387 579 1389 580 1392 581 1395 582 1397 583 1399 584 1401 585 1404 586 1407 587 1409 588 1411 589 1413 590 1416 591 1419 592 1421 593 1423 594 1425 595 1428 596 1431 597 1433 598 1435 599 1437 600 1440 601 1443 602 1445 603 1447 604 1449 605 1452 606 1455 607 1457 608 1459 609 1461 610 1464 611 1467 612 1469 613 1471 614 1473 615 1476 616 1479 617 1481 618 1483 619 1485 620 1488 621 1491 622 1493 623 1495 624 1497 625 1500 626 1503 627 1505 628 1507 629 1509 630 1512 631 1515 632 1517 633 1519 634 1521 635 1524 636 1527 637 1529 638 1531 639 1533 640 1536 641 1539 642 1541 643 1543 644 1545 645 1548 646 1551 647 1553 648 1555 649 1557 650 1560 651 1563 652 1565 653 1567 654 1569 655 1572 656 1575 657 1577 658 1579 659 1581 660 1584 661 1587 662 1589 663 1591 664 1593 665 1596 666 1599 667 1601 668 1603 669 1605 670 1608 671 1611 672 1613 673 1615 674 1617 675 1620 676 1623 677 1625 678 1627 679 1629 680 1632 681 1635 682 1637 683 1639 684 1641 685 1644 686 1647 687 1649 688 1651 689 1653 690 1656 691 1659 692 1661 693 1663 694 1665 695 1668 696 1671 697 1673 698 1675 699 1677 700 1680 701 1683 702 1685 703 1687 704 1689 705 1692 706 1695 707 1697 708 1699 709 1701 710 1704 711 1707 712 1709 713 1711 714 1713 715 1716 716 1719 717 1721 718 1723 719 1725 720 1728 721 1731 722 1733 723 1735 724 1737 725 1740 726 1743 727 1745 728 1747 729 1749 730 1752 731 1755 732 1757 733 1759 734 1761 735 1764 736 1767 737 1769 738 1771 739 1773 740 1776 741 1779 742 1781 743 1783 744 1785 745 1788 746 1791 747 1793 748 1795 749 1797 750 1800 751 1803 752 1805 753 1807 754 1809 755 1812 756 1815 757 1817 758 1819 759 1821 760 1824 761 1827 762 1829 763 1831 764 1833 765 1836 766 1839 767 1841 768 1843 769 1845 770 1848 771 1851 772 1853 773 1855 774 1857 775 1860 776 1863 777 1865 778 1867 779 1869 780 1872 781 1875 782 1877 783 1879 784 1881 785 1884 786 1887 787 1889 788 1891 789 1893 790 1896 791 1899 792 1901 793 1903 794 1905 795 1908 796 1911 797 1913 798 1915 799 1917 800 1920 801 1923 802 1925 803 1927 804 1929 805 1932 806 1935 807 1937 808 1939 809 1941 810 1944 811 1947 812 1949 813 1951 814 1953 815 1956 816 1959 817 1961 818 1963 819 1965 820 1968 821 1971 822 1973 823 1975 824 1977 825 1980 826 1983 827 1985 828 1987 829 1989 830 1992 831 1995 832 1997 833 1999 834 2001 835 2004 836 2007 837 2009 838 2011 839 2013 840 2016 841 2019 842 2021 843 2023 844 2025 845 2028 846 2031 847 2033 848 2035 849 2037 850 2040 851 2043 852 2045 853 2047 854 2049 855 2052 856 2055 857 2057 858 2059 859 2061 860 2064 861 2067 862 2069 863 2071 864 2073 865 2076 866 2079 867 2081 868 2083 869 2085 870 2088 871 2091 872 2093 873 2095 874 2097 875 2100 876 2103 877 2105 878 2107 879 2109 880 2112 881 2115 882 2117 883 2119 884 2121 885 2124 886 2127 887 2129 888 2131 889 2133 890 2136 891 2139 892 2141 893 2143 894 2145 895 2148 896 2151 897 2153 898 2155 899 2157 900 2160 901 2163 902 2165 903 2167 904 2169 905 2172 906 2175 907 2177 908 2179 909 2181 910 2184 911 2187 912 2189 913 2191 914 2193 915 2196 916 2199 917 2201 918 2203 919 2205 920 2208 921 2211 922 2213 923 2215 924 2217 925 2220 926 2223 927 2225 928 2227 929 2229 930 2232 931 2235 932 2237 933 2239 934 2241 935 2244 936 2247 937 2249 938 2251 939 2253 940 2256 941 2259 942 2261 943 2263 944 2265 945 2268 946 2271 947 2273 948 2275 949 2277 950 2280 951 2283 952 2285 953 2287 954 2289 955 2292 956 2295 957 2297 958 2299 959 2301 960 2304 961 2307 962 2309 963 2311 964 2313 965 2316 966 2319 967 2321 968 2323 969 2325 970 2328 971 2331 972 2333 973 2335 974 2337 975 2340 976 2343 977 2345 978 2347 979 2349 980 2352 981 2355 982 2357 983 2359 984 2361 985 2364 986 2367 987 2369 988 2371 989 2373 990 2376 991 2379 992 2381 993 2383 994 2385 995 2388 996 2391 997 2393 998 2395 999 2397