1 1 2 2 3 3 4 5 5 7 6 9 7 11 8 13 9 15 10 16 11 18 12 20 13 22 14 24 15 26 16 27 17 29 18 31 19 33 20 35 21 37 22 39 23 40 24 42 25 44 26 46 27 49 28 51 29 53 30 55 31 57 32 59 33 61 34 63 35 65 36 67 37 69 38 71 39 73 40 75 41 77 42 79 43 81 44 83 45 85 46 87 47 89 48 91 49 93 50 95 51 97 52 100 53 102 54 104 55 106 56 108 57 110 58 112 59 113 60 115 61 117 62 119 63 121 64 123 65 125 66 127 67 129 68 131 69 133 70 135 71 137 72 139 73 141 74 143 75 145 76 147 77 149 78 151 79 153 80 155 81 157 82 159 83 161 84 163 85 165 86 167 87 169 88 171 89 173 90 175 91 178 92 180 93 182 94 184 95 186 96 188 97 190 98 192 99 194 100 196 101 198 102 200 103 202 104 204 105 206 106 208 107 210 108 212 109 214 110 216 111 218 112 220 113 222 114 224 115 226 116 228 117 230 118 232 119 234 120 236 121 238 122 240 123 242 124 244 125 246 126 248 127 250 128 252 129 254 130 256 131 258 132 260 133 262 134 264 135 266 136 268 137 270 138 272 139 274 140 276 141 278 142 280 143 282 144 284 145 286 146 288 147 290 148 291 149 293 150 295 151 297 152 299 153 301 154 303 155 305 156 307 157 309 158 311 159 313 160 315 161 317 162 319 163 321 164 323 165 325 166 327 167 329 168 331 169 333 170 335 171 337 172 339 173 341 174 343 175 345 176 347 177 349 178 351 179 353 180 355 181 357 182 360 183 362 184 364 185 366 186 368 187 370 188 372 189 374 190 376 191 378 192 380 193 382 194 384 195 386 196 388 197 390 198 392 199 394 200 396 201 398 202 400 203 402 204 404 205 406 206 408 207 410 208 412 209 414 210 416 211 418 212 420 213 422 214 424 215 426 216 428 217 430 218 432 219 434 220 436 221 438 222 440 223 442 224 444 225 446 226 448 227 450 228 452 229 454 230 456 231 458 232 460 233 462 234 464 235 466 236 468 237 470 238 472 239 474 240 476 241 479 242 481 243 483 244 485 245 487 246 489 247 491 248 493 249 495 250 497 251 500 252 502 253 504 254 506 255 508 256 510 257 512 258 514 259 516 260 518 261 520 262 522 263 524 264 526 265 528 266 530 267 532 268 534 269 536 270 538 271 540 272 542 273 544 274 546 275 548 276 550 277 552 278 554 279 556 280 558 281 560 282 562 283 564 284 566 285 568 286 570 287 572 288 574 289 576 290 578 291 580 292 582 293 584 294 586 295 588 296 590 297 592 298 594 299 596 300 598 301 600 302 602 303 604 304 606 305 608 306 610 307 612 308 614 309 616 310 618 311 620 312 622 313 624 314 626 315 628 316 630 317 632 318 634 319 636 320 638 321 640 322 642 323 644 324 646 325 648 326 650 327 652 328 654 329 656 330 658 331 660 332 662 333 664 334 666 335 668 336 670 337 672 338 674 339 675 340 677 341 679 342 681 343 683 344 685 345 687 346 689 347 691 348 693 349 695 350 697 351 699 352 701 353 703 354 705 355 707 356 709 357 711 358 713 359 715 360 717 361 719 362 721 363 723 364 725 365 727 366 729 367 731 368 733 369 735 370 736 371 738 372 740 373 742 374 744 375 746 376 748 377 750 378 752 379 754 380 756 381 758 382 760 383 762 384 764 385 766 386 768 387 770 388 773 389 775 390 777 391 779 392 781 393 783 394 785 395 787 396 789 397 791 398 793 399 795 400 797 401 799 402 801 403 803 404 805 405 807 406 809 407 811 408 813 409 815 410 817 411 819 412 821 413 823 414 825 415 827 416 829 417 831 418 833 419 835 420 837 421 839 422 841 423 843 424 845 425 848 426 850 427 852 428 854 429 856 430 858 431 860 432 862 433 864 434 866 435 868 436 870 437 872 438 874 439 876 440 878 441 879 442 881 443 883 444 885 445 887 446 889 447 891 448 893 449 895 450 897 451 899 452 901 453 903 454 905 455 907 456 909 457 911 458 913 459 915 460 917 461 919 462 921 463 923 464 925 465 927 466 929 467 931 468 933 469 935 470 937 471 939 472 941 473 943 474 945 475 947 476 949 477 951 478 953 479 955 480 957 481 959 482 961 483 963 484 965 485 967 486 969 487 971 488 973 489 975 490 977 491 979 492 981 493 983 494 985 495 987 496 989 497 991 498 993 499 995 500 998 501 1000 502 1002 503 1004 504 1006 505 1008 506 1011 507 1013 508 1015 509 1017 510 1019 511 1021 512 1023 513 1025 514 1027 515 1029 516 1031 517 1033 518 1035 519 1037 520 1039 521 1041 522 1043 523 1045 524 1047 525 1049 526 1051 527 1053 528 1055 529 1057 530 1059 531 1061 532 1063 533 1065 534 1067 535 1069 536 1071 537 1073 538 1075 539 1077 540 1079 541 1081 542 1083 543 1085 544 1087 545 1089 546 1091 547 1093 548 1095 549 1097 550 1099 551 1101 552 1103 553 1105 554 1107 555 1109 556 1111 557 1113 558 1115 559 1117 560 1119 561 1121 562 1123 563 1125 564 1127 565 1129 566 1131 567 1133 568 1135 569 1137 570 1139 571 1141 572 1143 573 1145 574 1147 575 1149 576 1151 577 1153 578 1155 579 1157 580 1159 581 1161 582 1163 583 1165 584 1167 585 1169 586 1171 587 1173 588 1175 589 1177 590 1179 591 1181 592 1183 593 1185 594 1188 595 1190 596 1192 597 1194 598 1196 599 1198 600 1200 601 1202 602 1204 603 1206 604 1208 605 1210 606 1212 607 1214 608 1216 609 1218 610 1220 611 1222 612 1224 613 1226 614 1228 615 1230 616 1232 617 1234 618 1236 619 1238 620 1240 621 1242 622 1244 623 1246 624 1248 625 1250 626 1252 627 1254 628 1256 629 1258 630 1260 631 1262 632 1264 633 1266 634 1268 635 1270 636 1272 637 1274 638 1276 639 1278 640 1280 641 1282 642 1284 643 1286 644 1288 645 1290 646 1292 647 1294 648 1296 649 1298 650 1300 651 1302 652 1304 653 1306 654 1308 655 1310 656 1312 657 1314 658 1316 659 1318 660 1320 661 1322 662 1324 663 1326 664 1328 665 1330 666 1332 667 1334 668 1336 669 1338 670 1340 671 1342 672 1344 673 1346 674 1348 675 1350 676 1352 677 1354 678 1356 679 1358 680 1360 681 1362 682 1364 683 1366 684 1368 685 1370 686 1372 687 1374 688 1376 689 1378 690 1380 691 1382 692 1384 693 1386 694 1388 695 1390 696 1392 697 1394 698 1396 699 1398 700 1400 701 1402 702 1404 703 1406 704 1408 705 1411 706 1413 707 1415 708 1417 709 1419 710 1421 711 1423 712 1425 713 1427 714 1429 715 1431 716 1433 717 1435 718 1437 719 1439 720 1441 721 1443 722 1445 723 1447 724 1449 725 1451 726 1453 727 1455 728 1457 729 1459 730 1461 731 1463 732 1465 733 1467 734 1469 735 1471 736 1474 737 1476 738 1478 739 1480 740 1482 741 1484 742 1486 743 1488 744 1490 745 1492 746 1494 747 1496 748 1498 749 1500 750 1502 751 1504 752 1506 753 1508 754 1510 755 1512 756 1514 757 1516 758 1518 759 1520 760 1522 761 1524 762 1526 763 1528 764 1530 765 1532 766 1534 767 1536 768 1538 769 1540 770 1542 771 1544 772 1546 773 1548 774 1550 775 1552 776 1554 777 1556 778 1558 779 1560 780 1562 781 1564 782 1566 783 1568 784 1570 785 1572 786 1574 787 1576 788 1578 789 1580 790 1582 791 1584 792 1586 793 1588 794 1590 795 1592 796 1594 797 1596 798 1598 799 1600 800 1602 801 1603 802 1605 803 1607 804 1609 805 1611 806 1613 807 1615 808 1617 809 1619 810 1621 811 1623 812 1625 813 1627 814 1629 815 1631 816 1633 817 1635 818 1637 819 1639 820 1641 821 1643 822 1645 823 1647 824 1649 825 1651 826 1653 827 1655 828 1657 829 1659 830 1661 831 1663 832 1665 833 1667 834 1669 835 1671 836 1673 837 1675 838 1677 839 1679 840 1681 841 1683 842 1685 843 1687 844 1689 845 1691 846 1693 847 1695 848 1697 849 1699 850 1701 851 1703 852 1705 853 1707 854 1709 855 1711 856 1713 857 1715 858 1717 859 1719 860 1721 861 1723 862 1725 863 1728 864 1730 865 1732 866 1734 867 1736 868 1738 869 1740 870 1742 871 1744 872 1746 873 1748 874 1750 875 1752 876 1754 877 1756 878 1758 879 1760 880 1762 881 1764 882 1766 883 1768 884 1770 885 1772 886 1774 887 1776 888 1778 889 1781 890 1783 891 1785 892 1787 893 1789 894 1791 895 1793 896 1795 897 1797 898 1799 899 1801 900 1803 901 1805 902 1807 903 1809 904 1811 905 1813 906 1815 907 1817 908 1819 909 1821 910 1823 911 1825 912 1827 913 1829 914 1831 915 1833 916 1835 917 1837 918 1839 919 1841 920 1843 921 1845 922 1847 923 1849 924 1850 925 1852 926 1854 927 1856 928 1858 929 1860 930 1862 931 1864 932 1866 933 1868 934 1870 935 1872 936 1874 937 1876 938 1878 939 1880 940 1882 941 1884 942 1886 943 1888 944 1890 945 1892 946 1894 947 1896 948 1898 949 1900 950 1902 951 1904 952 1906 953 1908 954 1910 955 1912 956 1914 957 1916 958 1918 959 1920 960 1922 961 1924 962 1926 963 1928 964 1930 965 1932 966 1934 967 1936 968 1938 969 1940 970 1942 971 1944 972 1946 973 1948 974 1950 975 1952 976 1954 977 1956 978 1958 979 1960 980 1962 981 1964 982 1966 983 1968 984 1970 985 1972 986 1974 987 1976 988 1978 989 1980 990 1982 991 1984 992 1986 993 1988 994 1990 995 1992 996 1994 997 1996 998 1998 999 2000 1000 2002