0 1 1 3 2 6 3 9 4 9 5 12 6 15 7 18 8 18 9 21 10 24 11 27 12 27 13 27 14 30 15 33 16 36 17 36 18 39 19 42 20 45 21 45 22 48 23 51 24 54 25 54 26 54 27 57 28 60 29 63 30 63 31 66 32 69 33 72 34 72 35 75 36 78 37 81 38 81 39 81 40 81 41 84 42 87 43 90 44 90 45 93 46 96 47 99 48 99 49 102 50 105 51 108 52 108 53 108 54 111 55 114 56 117 57 117 58 120 59 123 60 126 61 126 62 129 63 132 64 135 65 135 66 135 67 138 68 141 69 144 70 144 71 147 72 150 73 153 74 153 75 156 76 159 77 162 78 162 79 162 80 162 81 165 82 168 83 171 84 171 85 174 86 177 87 180 88 180 89 183 90 186 91 189 92 189 93 189 94 192 95 195 96 198 97 198 98 201 99 204 100 207 101 207 102 210 103 213 104 216 105 216 106 216 107 219 108 222 109 225 110 225 111 228 112 231 113 234 114 234 115 237 116 240 117 243 118 243 119 243 120 243 121 243 122 246 123 249 124 252 125 252 126 255 127 258 128 261 129 261 130 264 131 267 132 270 133 270 134 270 135 273 136 276 137 279 138 279 139 282 140 285 141 288 142 288 143 291 144 294 145 297 146 297 147 297 148 300 149 303 150 306 151 306 152 309 153 312 154 315 155 315 156 318 157 321 158 324 159 324 160 324 161 324 162 327 163 330 164 333 165 333 166 336 167 339 168 342 169 342 170 345 171 348 172 351 173 351 174 351 175 354 176 357 177 360 178 360 179 363 180 366 181 369 182 369 183 372 184 375 185 378 186 378 187 378 188 381 189 384 190 387 191 387 192 390 193 393 194 396 195 396 196 399 197 402 198 405 199 405 200 405 201 405 202 408 203 411 204 414 205 414 206 417 207 420 208 423 209 423 210 426 211 429 212 432 213 432 214 432 215 435 216 438 217 441 218 441 219 444 220 447 221 450 222 450 223 453 224 456 225 459 226 459 227 459 228 462 229 465 230 468 231 468 232 471 233 474 234 477 235 477 236 480 237 483 238 486 239 486 240 486 241 486 242 486 243 489 244 492 245 495 246 495 247 498 248 501 249 504 250 504 251 507 252 510 253 513 254 513 255 513 256 516 257 519 258 522 259 522 260 525 261 528 262 531 263 531 264 534 265 537 266 540 267 540 268 540 269 543 270 546 271 549 272 549 273 552 274 555 275 558 276 558 277 561 278 564 279 567 280 567 281 567 282 567 283 570 284 573 285 576 286 576 287 579 288 582 289 585 290 585 291 588 292 591 293 594 294 594 295 594 296 597 297 600 298 603 299 603 300 606 301 609 302 612 303 612 304 615 305 618 306 621 307 621 308 621 309 624 310 627 311 630 312 630 313 633 314 636 315 639 316 639 317 642 318 645 319 648 320 648 321 648 322 648 323 651 324 654 325 657 326 657 327 660 328 663 329 666 330 666 331 669 332 672 333 675 334 675 335 675 336 678 337 681 338 684 339 684 340 687 341 690 342 693 343 693 344 696 345 699 346 702 347 702 348 702 349 705 350 708 351 711 352 711 353 714 354 717 355 720 356 720 357 723 358 726 359 729 360 729 361 729 362 729 363 729 364 729 365 732 366 735 367 738 368 738 369 741 370 744 371 747 372 747 373 750 374 753 375 756 376 756 377 756 378 759 379 762 380 765 381 765 382 768 383 771 384 774 385 774 386 777 387 780 388 783 389 783 390 783 391 786 392 789 393 792 394 792 395 795 396 798 397 801 398 801 399 804 400 807 401 810 402 810 403 810 404 810 405 813 406 816 407 819 408 819 409 822 410 825 411 828 412 828 413 831 414 834 415 837 416 837 417 837 418 840 419 843 420 846 421 846 422 849 423 852 424 855 425 855 426 858 427 861 428 864 429 864 430 864 431 867 432 870 433 873 434 873 435 876 436 879 437 882 438 882 439 885 440 888 441 891 442 891 443 891 444 891 445 894 446 897 447 900 448 900 449 903 450 906 451 909 452 909 453 912 454 915 455 918 456 918 457 918 458 921 459 924 460 927 461 927 462 930 463 933 464 936 465 936 466 939 467 942 468 945 469 945 470 945 471 948 472 951 473 954 474 954 475 957 476 960 477 963 478 963 479 966 480 969 481 972 482 972 483 972 484 972 485 972 486 975 487 978 488 981 489 981 490 984 491 987 492 990 493 990 494 993 495 996 496 999 497 999 498 999 499 1002 500 1005 501 1008 502 1008 503 1011 504 1014 505 1017 506 1017 507 1020 508 1023 509 1026 510 1026 511 1026 512 1029 513 1032 514 1035 515 1035 516 1038 517 1041 518 1044 519 1044 520 1047 521 1050 522 1053 523 1053 524 1053 525 1053 526 1056 527 1059 528 1062 529 1062 530 1065 531 1068 532 1071 533 1071 534 1074 535 1077 536 1080 537 1080 538 1080 539 1083 540 1086 541 1089 542 1089 543 1092 544 1095 545 1098 546 1098 547 1101 548 1104 549 1107 550 1107 551 1107 552 1110 553 1113 554 1116 555 1116 556 1119 557 1122 558 1125 559 1125 560 1128 561 1131 562 1134 563 1134 564 1134 565 1134 566 1137 567 1140 568 1143 569 1143 570 1146 571 1149 572 1152 573 1152 574 1155 575 1158 576 1161 577 1161 578 1161 579 1164 580 1167 581 1170 582 1170 583 1173 584 1176 585 1179 586 1179 587 1182 588 1185 589 1188 590 1188 591 1188 592 1191 593 1194 594 1197 595 1197 596 1200 597 1203 598 1206 599 1206 600 1209 601 1212 602 1215 603 1215 604 1215 605 1215 606 1215 607 1218 608 1221 609 1224 610 1224 611 1227 612 1230 613 1233 614 1233 615 1236 616 1239 617 1242 618 1242 619 1242 620 1245 621 1248 622 1251 623 1251 624 1254 625 1257 626 1260 627 1260 628 1263 629 1266 630 1269 631 1269 632 1269 633 1272 634 1275 635 1278 636 1278 637 1281 638 1284 639 1287 640 1287 641 1290 642 1293 643 1296 644 1296 645 1296 646 1296 647 1299 648 1302 649 1305 650 1305 651 1308 652 1311 653 1314 654 1314 655 1317 656 1320 657 1323 658 1323 659 1323 660 1326 661 1329 662 1332 663 1332 664 1335 665 1338 666 1341 667 1341 668 1344 669 1347 670 1350 671 1350 672 1350 673 1353 674 1356 675 1359 676 1359 677 1362 678 1365 679 1368 680 1368 681 1371 682 1374 683 1377 684 1377 685 1377 686 1377 687 1380 688 1383 689 1386 690 1386 691 1389 692 1392 693 1395 694 1395 695 1398 696 1401 697 1404 698 1404 699 1404 700 1407 701 1410 702 1413 703 1413 704 1416 705 1419 706 1422 707 1422 708 1425 709 1428 710 1431 711 1431 712 1431 713 1434 714 1437 715 1440 716 1440 717 1443 718 1446 719 1449 720 1449 721 1452 722 1455 723 1458 724 1458 725 1458 726 1458 727 1458 728 1458 729 1461 730 1464 731 1467 732 1467 733 1470 734 1473 735 1476 736 1476 737 1479 738 1482 739 1485 740 1485 741 1485 742 1488 743 1491 744 1494 745 1494 746 1497 747 1500 748 1503 749 1503 750 1506 751 1509 752 1512 753 1512 754 1512 755 1515 756 1518 757 1521 758 1521 759 1524 760 1527 761 1530 762 1530 763 1533 764 1536 765 1539 766 1539 767 1539 768 1539 769 1542 770 1545 771 1548 772 1548 773 1551 774 1554 775 1557 776 1557 777 1560 778 1563 779 1566 780 1566 781 1566 782 1569 783 1572 784 1575 785 1575 786 1578 787 1581 788 1584 789 1584 790 1587 791 1590 792 1593 793 1593 794 1593 795 1596 796 1599 797 1602 798 1602 799 1605 800 1608 801 1611 802 1611 803 1614 804 1617 805 1620 806 1620 807 1620 808 1620 809 1623 810 1626 811 1629 812 1629 813 1632 814 1635 815 1638 816 1638 817 1641 818 1644 819 1647 820 1647 821 1647 822 1650 823 1653 824 1656 825 1656 826 1659 827 1662 828 1665 829 1665 830 1668 831 1671 832 1674 833 1674 834 1674 835 1677 836 1680 837 1683 838 1683 839 1686 840 1689 841 1692 842 1692 843 1695 844 1698 845 1701 846 1701 847 1701 848 1701 849 1701 850 1704 851 1707 852 1710 853 1710 854 1713 855 1716 856 1719 857 1719 858 1722 859 1725 860 1728 861 1728 862 1728 863 1731 864 1734 865 1737 866 1737 867 1740 868 1743 869 1746 870 1746 871 1749 872 1752 873 1755 874 1755 875 1755 876 1758 877 1761 878 1764 879 1764 880 1767 881 1770 882 1773 883 1773 884 1776 885 1779 886 1782 887 1782 888 1782 889 1782 890 1785 891 1788 892 1791 893 1791 894 1794 895 1797 896 1800 897 1800 898 1803 899 1806 900 1809 901 1809 902 1809 903 1812 904 1815 905 1818 906 1818 907 1821 908 1824 909 1827 910 1827 911 1830 912 1833 913 1836 914 1836 915 1836 916 1839 917 1842 918 1845 919 1845 920 1848 921 1851 922 1854 923 1854 924 1857 925 1860 926 1863 927 1863 928 1863 929 1863 930 1866 931 1869 932 1872 933 1872 934 1875 935 1878 936 1881 937 1881 938 1884 939 1887 940 1890 941 1890 942 1890 943 1893 944 1896 945 1899 946 1899 947 1902 948 1905 949 1908 950 1908 951 1911 952 1914 953 1917 954 1917 955 1917 956 1920 957 1923 958 1926 959 1926 960 1929 961 1932 962 1935 963 1935 964 1938 965 1941 966 1944 967 1944 968 1944 969 1944 970 1944 971 1947 972 1950 973 1953 974 1953 975 1956 976 1959 977 1962 978 1962 979 1965 980 1968 981 1971 982 1971 983 1971 984 1974 985 1977 986 1980 987 1980 988 1983 989 1986 990 1989 991 1989 992 1992 993 1995 994 1998 995 1998 996 1998 997 2001 998 2004 999 2007 1000 2007