1 1 2 2 3 4 4 7 5 8 6 13 7 14 8 16 9 17 10 19 11 23 12 26 13 28 14 29 15 31 16 32 17 34 18 37 19 38 20 41 21 43 22 46 23 47 24 49 25 52 26 53 27 56 28 58 29 59 30 61 31 62 32 64 33 67 34 68 35 71 36 73 37 74 38 76 39 79 40 82 41 83 42 86 43 89 44 91 45 92 46 94 47 97 48 98 49 101 50 103 51 104 52 106 53 107 54 109 55 112 56 113 57 116 58 118 59 119 60 122 61 124 62 127 63 128 64 131 65 133 66 134 67 136 68 137 69 139 70 142 71 146 72 148 73 149 74 151 75 152 76 157 77 158 78 161 79 163 80 164 81 166 82 167 83 169 84 172 85 173 86 178 87 179 88 181 89 182 90 184 91 188 92 191 93 193 94 194 95 196 96 197 97 199 98 202 99 203 100 206 101 208 102 211 103 212 104 214 105 217 106 218 107 221 108 223 109 224 110 226 111 227 112 229 113 232 114 233 115 236 116 238 117 239 118 241 119 244 120 247 121 248 122 251 123 254 124 256 125 257 126 259 127 262 128 263 129 266 130 268 131 269 132 271 133 272 134 274 135 277 136 278 137 281 138 283 139 284 140 287 141 289 142 292 143 293 144 296 145 298 146 299 147 301 148 302 149 304 150 307 151 311 152 313 153 314 154 316 155 317 156 322 157 323 158 326 159 328 160 329 161 331 162 332 163 334 164 337 165 338 166 343 167 344 168 346 169 347 170 349 171 353 172 356 173 358 174 359 175 361 176 362 177 364 178 367 179 368 180 371 181 373 182 376 183 377 184 379 185 382 186 383 187 386 188 388 189 389 190 391 191 392 192 394 193 397 194 398 195 401 196 403 197 404 198 406 199 409 200 412 201 413 202 416 203 419 204 421 205 422 206 424 207 427 208 428 209 431 210 433 211 434 212 436 213 437 214 439 215 442 216 443 217 446 218 448 219 449 220 452 221 454 222 457 223 458 224 461 225 463 226 464 227 466 228 467 229 469 230 472 231 476 232 478 233 479 234 481 235 482 236 487 237 488 238 491 239 493 240 494 241 496 242 497 243 499 244 502 245 503 246 508 247 509 248 511 249 512 250 514 251 518 252 521 253 523 254 524 255 526 256 527 257 529 258 532 259 533 260 536 261 538 262 541 263 542 264 544 265 547 266 548 267 551 268 553 269 554 270 556 271 557 272 559 273 562 274 563 275 566 276 568 277 569 278 571 279 574 280 577 281 578 282 581 283 584 284 586 285 587 286 589 287 592 288 593 289 596 290 598 291 599 292 601 293 602 294 604 295 607 296 608 297 611 298 613 299 614 300 617 301 619 302 622 303 623 304 626 305 628 306 629 307 631 308 632 309 634 310 637 311 641 312 643 313 644 314 646 315 647 316 652 317 653 318 656 319 658 320 659 321 661 322 662 323 664 324 667 325 668 326 673 327 674 328 676 329 677 330 679 331 683 332 686 333 688 334 689 335 691 336 692 337 694 338 697 339 698 340 701 341 703 342 706 343 707 344 709 345 712 346 713 347 716 348 718 349 719 350 721 351 722 352 724 353 727 354 728 355 731 356 733 357 734 358 736 359 739 360 742 361 743 362 746 363 749 364 751 365 752 366 754 367 757 368 758 369 761 370 763 371 764 372 766 373 767 374 769 375 772 376 773 377 776 378 778 379 779 380 782 381 784 382 787 383 788 384 791 385 793 386 794 387 796 388 797 389 799 390 802 391 806 392 808 393 809 394 811 395 812 396 817 397 818 398 821 399 823 400 824 401 826 402 827 403 829 404 832 405 833 406 838 407 839 408 841 409 842 410 844 411 848 412 851 413 853 414 854 415 856 416 857 417 859 418 862 419 863 420 866 421 868 422 871 423 872 424 874 425 877 426 878 427 881 428 883 429 884 430 886 431 887 432 889 433 892 434 893 435 896 436 898 437 899 438 901 439 904 440 907 441 908 442 911 443 914 444 916 445 917 446 919 447 922 448 923 449 926 450 928 451 929 452 931 453 932 454 934 455 937 456 938 457 941 458 943 459 944 460 947 461 949 462 952 463 953 464 956 465 958 466 959 467 961 468 962 469 964 470 967 471 971 472 973 473 974 474 976 475 977 476 982 477 983 478 986 479 988 480 989 481 991 482 992 483 994 484 997 485 998 486 1003 487 1004 488 1006 489 1007 490 1009 491 1013 492 1016 493 1018 494 1019 495 1021 496 1022 497 1024 498 1027 499 1028 500 1031 501 1033 502 1036 503 1037 504 1039 505 1042 506 1043 507 1046 508 1048 509 1049 510 1051 511 1052 512 1054 513 1057 514 1058 515 1061 516 1063 517 1064 518 1066 519 1069 520 1072 521 1073 522 1076 523 1079 524 1081 525 1082 526 1084 527 1087 528 1088 529 1091 530 1093 531 1094 532 1096 533 1097 534 1099 535 1102 536 1103 537 1106 538 1108 539 1109 540 1112 541 1114 542 1117 543 1118 544 1121 545 1123 546 1124 547 1126 548 1127 549 1129 550 1132 551 1136 552 1138 553 1139 554 1141 555 1142 556 1147 557 1148 558 1151 559 1153 560 1154 561 1156 562 1157 563 1159 564 1162 565 1163 566 1168 567 1169 568 1171 569 1172 570 1174 571 1178 572 1181 573 1183 574 1184 575 1186 576 1187 577 1189 578 1192 579 1193 580 1196 581 1198 582 1201 583 1202 584 1204 585 1207 586 1208 587 1211 588 1213 589 1214 590 1216 591 1217 592 1219 593 1222 594 1223 595 1226 596 1228 597 1229 598 1231 599 1234 600 1237 601 1238 602 1241 603 1244 604 1246 605 1247 606 1249 607 1252 608 1253 609 1256 610 1258 611 1259 612 1261 613 1262 614 1264 615 1267 616 1268 617 1271 618 1273 619 1274 620 1277 621 1279 622 1282 623 1283 624 1286 625 1288 626 1289 627 1291 628 1292 629 1294 630 1297 631 1301 632 1303 633 1304 634 1306 635 1307 636 1312 637 1313 638 1316 639 1318 640 1319 641 1321 642 1322 643 1324 644 1327 645 1328 646 1333 647 1334 648 1336 649 1337 650 1339 651 1343 652 1346 653 1348 654 1349 655 1351 656 1352 657 1354 658 1357 659 1358 660 1361 661 1363 662 1366 663 1367 664 1369 665 1372 666 1373 667 1376 668 1378 669 1379 670 1381 671 1382 672 1384 673 1387 674 1388 675 1391 676 1393 677 1394 678 1396 679 1399 680 1402 681 1403 682 1406 683 1409 684 1411 685 1412 686 1414 687 1417 688 1418 689 1421 690 1423 691 1424 692 1426 693 1427 694 1429 695 1432 696 1433 697 1436 698 1438 699 1439 700 1442 701 1444 702 1447 703 1448 704 1451 705 1453 706 1454 707 1456 708 1457 709 1459 710 1462 711 1466 712 1468 713 1469 714 1471 715 1472 716 1477 717 1478 718 1481 719 1483 720 1484 721 1486 722 1487 723 1489 724 1492 725 1493 726 1498 727 1499 728 1501 729 1502 730 1504 731 1508 732 1511 733 1513 734 1514 735 1516 736 1517 737 1519 738 1522 739 1523 740 1526 741 1528 742 1531 743 1532 744 1534 745 1537 746 1538 747 1541 748 1543 749 1544 750 1546 751 1547 752 1549 753 1552 754 1553 755 1556 756 1558 757 1559 758 1561 759 1564 760 1567 761 1568 762 1571 763 1574 764 1576 765 1577 766 1579 767 1582 768 1583 769 1586 770 1588 771 1589 772 1591 773 1592 774 1594 775 1597 776 1598 777 1601 778 1603 779 1604 780 1607 781 1609 782 1612 783 1613 784 1616 785 1618 786 1619 787 1621 788 1622 789 1624 790 1627 791 1631 792 1633 793 1634 794 1636 795 1637 796 1642 797 1643 798 1646 799 1648 800 1649 801 1651 802 1652 803 1654 804 1657 805 1658 806 1663 807 1664 808 1666 809 1667 810 1669 811 1673 812 1676 813 1678 814 1679 815 1681 816 1682 817 1684 818 1687 819 1688 820 1691 821 1693 822 1696 823 1697 824 1699 825 1702 826 1703 827 1706 828 1708 829 1709 830 1711 831 1712 832 1714 833 1717 834 1718 835 1721 836 1723 837 1724 838 1726 839 1729 840 1732 841 1733 842 1736 843 1739 844 1741 845 1742 846 1744 847 1747 848 1748 849 1751 850 1753 851 1754 852 1756 853 1757 854 1759 855 1762 856 1763 857 1766 858 1768 859 1769 860 1772 861 1774 862 1777 863 1778 864 1781 865 1783 866 1784 867 1786 868 1787 869 1789 870 1792 871 1796 872 1798 873 1799 874 1801 875 1802 876 1807 877 1808 878 1811 879 1813 880 1814 881 1816 882 1817 883 1819 884 1822 885 1823 886 1828 887 1829 888 1831 889 1832 890 1834 891 1838 892 1841 893 1843 894 1844 895 1846 896 1847 897 1849 898 1852 899 1853 900 1856 901 1858 902 1861 903 1862 904 1864 905 1867 906 1868 907 1871 908 1873 909 1874 910 1876 911 1877 912 1879 913 1882 914 1883 915 1886 916 1888 917 1889 918 1891 919 1894 920 1897 921 1898 922 1901 923 1904 924 1906 925 1907 926 1909 927 1912 928 1913 929 1916 930 1918 931 1919 932 1921 933 1922 934 1924 935 1927 936 1928 937 1931 938 1933 939 1934 940 1937 941 1939 942 1942 943 1943 944 1946 945 1948 946 1949 947 1951 948 1952 949 1954 950 1957 951 1961 952 1963 953 1964 954 1966 955 1967 956 1972 957 1973 958 1976 959 1978 960 1979 961 1981 962 1982 963 1984 964 1987 965 1988 966 1993 967 1994 968 1996 969 1997 970 1999 971 2003 972 2006 973 2008 974 2009 975 2011 976 2012 977 2014 978 2017 979 2018 980 2021 981 2023 982 2026 983 2027 984 2029 985 2032 986 2033 987 2036 988 2038 989 2039 990 2041 991 2042 992 2044 993 2047 994 2048 995 2051 996 2053 997 2054 998 2056 999 2059 1000 2062