1 1 2 3 3 4 4 7 5 9 6 11 7 12 8 15 9 17 10 19 11 20 12 23 13 25 14 27 15 28 16 31 17 33 18 35 19 36 20 39 21 41 22 43 23 44 24 47 25 49 26 51 27 52 28 55 29 57 30 59 31 60 32 63 33 65 34 67 35 68 36 71 37 73 38 75 39 76 40 79 41 81 42 83 43 84 44 87 45 89 46 91 47 92 48 95 49 97 50 99 51 100 52 103 53 105 54 107 55 108 56 111 57 113 58 115 59 116 60 119 61 121 62 123 63 124 64 127 65 129 66 131 67 132 68 135 69 137 70 139 71 140 72 143 73 145 74 147 75 148 76 151 77 153 78 155 79 156 80 159 81 161 82 163 83 164 84 167 85 169 86 171 87 172 88 175 89 177 90 179 91 180 92 183 93 185 94 187 95 188 96 191 97 193 98 195 99 196 100 199 101 201 102 203 103 204 104 207 105 209 106 211 107 212 108 215 109 217 110 219 111 220 112 223 113 225 114 227 115 228 116 231 117 233 118 235 119 236 120 239 121 241 122 243 123 244 124 247 125 249 126 251 127 252 128 255 129 257 130 259 131 260 132 263 133 265 134 267 135 268 136 271 137 273 138 275 139 276 140 279 141 281 142 283 143 284 144 287 145 289 146 291 147 292 148 295 149 297 150 299 151 300 152 303 153 305 154 307 155 308 156 311 157 313 158 315 159 316 160 319 161 321 162 323 163 324 164 327 165 329 166 331 167 332 168 335 169 337 170 339 171 340 172 343 173 345 174 347 175 348 176 351 177 353 178 355 179 356 180 359 181 361 182 363 183 364 184 367 185 369 186 371 187 372 188 375 189 377 190 379 191 380 192 383 193 385 194 387 195 388 196 391 197 393 198 395 199 396 200 399 201 401 202 403 203 404 204 407 205 409 206 411 207 412 208 415 209 417 210 419 211 420 212 423 213 425 214 427 215 428 216 431 217 433 218 435 219 436 220 439 221 441 222 443 223 444 224 447 225 449 226 451 227 452 228 455 229 457 230 459 231 460 232 463 233 465 234 467 235 468 236 471 237 473 238 475 239 476 240 479 241 481 242 483 243 484 244 487 245 489 246 491 247 492 248 495 249 497 250 499 251 500 252 503 253 505 254 507 255 508 256 511 257 513 258 515 259 516 260 519 261 521 262 523 263 524 264 527 265 529 266 531 267 532 268 535 269 537 270 539 271 540 272 543 273 545 274 547 275 548 276 551 277 553 278 555 279 556 280 559 281 561 282 563 283 564 284 567 285 569 286 571 287 572 288 575 289 577 290 579 291 580 292 583 293 585 294 587 295 588 296 591 297 593 298 595 299 596 300 599 301 601 302 603 303 604 304 607 305 609 306 611 307 612 308 615 309 617 310 619 311 620 312 623 313 625 314 627 315 628 316 631 317 633 318 635 319 636 320 639 321 641 322 643 323 644 324 647 325 649 326 651 327 652 328 655 329 657 330 659 331 660 332 663 333 665 334 667 335 668 336 671 337 673 338 675 339 676 340 679 341 681 342 683 343 684 344 687 345 689 346 691 347 692 348 695 349 697 350 699 351 700 352 703 353 705 354 707 355 708 356 711 357 713 358 715 359 716 360 719 361 721 362 723 363 724 364 727 365 729 366 731 367 732 368 735 369 737 370 739 371 740 372 743 373 745 374 747 375 748 376 751 377 753 378 755 379 756 380 759 381 761 382 763 383 764 384 767 385 769 386 771 387 772 388 775 389 777 390 779 391 780 392 783 393 785 394 787 395 788 396 791 397 793 398 795 399 796 400 799 401 801 402 803 403 804 404 807 405 809 406 811 407 812 408 815 409 817 410 819 411 820 412 823 413 825 414 827 415 828 416 831 417 833 418 835 419 836 420 839 421 841 422 843 423 844 424 847 425 849 426 851 427 852 428 855 429 857 430 859 431 860 432 863 433 865 434 867 435 868 436 871 437 873 438 875 439 876 440 879 441 881 442 883 443 884 444 887 445 889 446 891 447 892 448 895 449 897 450 899 451 900 452 903 453 905 454 907 455 908 456 911 457 913 458 915 459 916 460 919 461 921 462 923 463 924 464 927 465 929 466 931 467 932 468 935 469 937 470 939 471 940 472 943 473 945 474 947 475 948 476 951 477 953 478 955 479 956 480 959 481 961 482 963 483 964 484 967 485 969 486 971 487 972 488 975 489 977 490 979 491 980 492 983 493 985 494 987 495 988 496 991 497 993 498 995 499 996 500 999 501 1001 502 1003 503 1004 504 1007 505 1009 506 1011 507 1012 508 1015 509 1017 510 1019 511 1020 512 1023 513 1025 514 1027 515 1028 516 1031 517 1033 518 1035 519 1036 520 1039 521 1041 522 1043 523 1044 524 1047 525 1049 526 1051 527 1052 528 1055 529 1057 530 1059 531 1060 532 1063 533 1065 534 1067 535 1068 536 1071 537 1073 538 1075 539 1076 540 1079 541 1081 542 1083 543 1084 544 1087 545 1089 546 1091 547 1092 548 1095 549 1097 550 1099 551 1100 552 1103 553 1105 554 1107 555 1108 556 1111 557 1113 558 1115 559 1116 560 1119 561 1121 562 1123 563 1124 564 1127 565 1129 566 1131 567 1132 568 1135 569 1137 570 1139 571 1140 572 1143 573 1145 574 1147 575 1148 576 1151 577 1153 578 1155 579 1156 580 1159 581 1161 582 1163 583 1164 584 1167 585 1169 586 1171 587 1172 588 1175 589 1177 590 1179 591 1180 592 1183 593 1185 594 1187 595 1188 596 1191 597 1193 598 1195 599 1196 600 1199 601 1201 602 1203 603 1204 604 1207 605 1209 606 1211 607 1212 608 1215 609 1217 610 1219 611 1220 612 1223 613 1225 614 1227 615 1228 616 1231 617 1233 618 1235 619 1236 620 1239 621 1241 622 1243 623 1244 624 1247 625 1249 626 1251 627 1252 628 1255 629 1257 630 1259 631 1260 632 1263 633 1265 634 1267 635 1268 636 1271 637 1273 638 1275 639 1276 640 1279 641 1281 642 1283 643 1284 644 1287 645 1289 646 1291 647 1292 648 1295 649 1297 650 1299 651 1300 652 1303 653 1305 654 1307 655 1308 656 1311 657 1313 658 1315 659 1316 660 1319 661 1321 662 1323 663 1324 664 1327 665 1329 666 1331 667 1332 668 1335 669 1337 670 1339 671 1340 672 1343 673 1345 674 1347 675 1348 676 1351 677 1353 678 1355 679 1356 680 1359 681 1361 682 1363 683 1364 684 1367 685 1369 686 1371 687 1372 688 1375 689 1377 690 1379 691 1380 692 1383 693 1385 694 1387 695 1388 696 1391 697 1393 698 1395 699 1396 700 1399 701 1401 702 1403 703 1404 704 1407 705 1409 706 1411 707 1412 708 1415 709 1417 710 1419 711 1420 712 1423 713 1425 714 1427 715 1428 716 1431 717 1433 718 1435 719 1436 720 1439 721 1441 722 1443 723 1444 724 1447 725 1449 726 1451 727 1452 728 1455 729 1457 730 1459 731 1460 732 1463 733 1465 734 1467 735 1468 736 1471 737 1473 738 1475 739 1476 740 1479 741 1481 742 1483 743 1484 744 1487 745 1489 746 1491 747 1492 748 1495 749 1497 750 1499 751 1500 752 1503 753 1505 754 1507 755 1508 756 1511 757 1513 758 1515 759 1516 760 1519 761 1521 762 1523 763 1524 764 1527 765 1529 766 1531 767 1532 768 1535 769 1537 770 1539 771 1540 772 1543 773 1545 774 1547 775 1548 776 1551 777 1553 778 1555 779 1556 780 1559 781 1561 782 1563 783 1564 784 1567 785 1569 786 1571 787 1572 788 1575 789 1577 790 1579 791 1580 792 1583 793 1585 794 1587 795 1588 796 1591 797 1593 798 1595 799 1596 800 1599 801 1601 802 1603 803 1604 804 1607 805 1609 806 1611 807 1612 808 1615 809 1617 810 1619 811 1620 812 1623 813 1625 814 1627 815 1628 816 1631 817 1633 818 1635 819 1636 820 1639 821 1641 822 1643 823 1644 824 1647 825 1649 826 1651 827 1652 828 1655 829 1657 830 1659 831 1660 832 1663 833 1665 834 1667 835 1668 836 1671 837 1673 838 1675 839 1676 840 1679 841 1681 842 1683 843 1684 844 1687 845 1689 846 1691 847 1692 848 1695 849 1697 850 1699 851 1700 852 1703 853 1705 854 1707 855 1708 856 1711 857 1713 858 1715 859 1716 860 1719 861 1721 862 1723 863 1724 864 1727 865 1729 866 1731 867 1732 868 1735 869 1737 870 1739 871 1740 872 1743 873 1745 874 1747 875 1748 876 1751 877 1753 878 1755 879 1756 880 1759 881 1761 882 1763 883 1764 884 1767 885 1769 886 1771 887 1772 888 1775 889 1777 890 1779 891 1780 892 1783 893 1785 894 1787 895 1788 896 1791 897 1793 898 1795 899 1796 900 1799 901 1801 902 1803 903 1804 904 1807 905 1809 906 1811 907 1812 908 1815 909 1817 910 1819 911 1820 912 1823 913 1825 914 1827 915 1828 916 1831 917 1833 918 1835 919 1836 920 1839 921 1841 922 1843 923 1844 924 1847 925 1849 926 1851 927 1852 928 1855 929 1857 930 1859 931 1860 932 1863 933 1865 934 1867 935 1868 936 1871 937 1873 938 1875 939 1876 940 1879 941 1881 942 1883 943 1884 944 1887 945 1889 946 1891 947 1892 948 1895 949 1897 950 1899 951 1900 952 1903 953 1905 954 1907 955 1908 956 1911 957 1913 958 1915 959 1916 960 1919 961 1921 962 1923 963 1924 964 1927 965 1929 966 1931 967 1932 968 1935 969 1937 970 1939 971 1940 972 1943 973 1945 974 1947 975 1948 976 1951 977 1953 978 1955 979 1956 980 1959 981 1961 982 1963 983 1964 984 1967 985 1969 986 1971 987 1972 988 1975 989 1977 990 1979 991 1980 992 1983 993 1985 994 1987 995 1988 996 1991 997 1993 998 1995 999 1996 1000 1999