1 1 2 2 3 5 4 3 5 8 6 6 7 21 8 4 9 13 10 11 11 9 12 30 13 7 14 24 15 22 16 71 17 20 18 18 19 16 20 14 21 45 22 12 23 39 24 10 25 33 26 31 27 106 28 104 29 29 30 27 31 25 32 82 33 23 34 74 35 72 36 251 37 249 38 70 39 68 40 19 41 62 42 17 43 54 44 15 45 48 46 46 47 163 48 161 49 44 50 42 51 40 52 139 53 38 54 36 55 34 56 117 57 115 58 32 59 109 60 107 61 366 62 105 63 360 64 103 65 101 66 99 67 28 68 91 69 26 70 85 71 83 72 290 73 81 74 79 75 77 76 75 77 260 78 73 79 254 80 252 81 895 82 250 83 889 84 248 85 246 86 244 87 69 88 238 89 67 90 65 91 63 92 218 93 61 94 59 95 57 96 55 97 192 98 53 99 51 100 49 101 174 102 47 103 168 104 166 105 164 106 567 107 162 108 561 109 160 110 158 111 43 112 152 113 150 114 41 115 142 116 140 117 485 118 138 119 136 120 37 121 130 122 35 123 122 124 120 125 118 126 407 127 116 128 399 129 114 130 112 131 110 132 377 133 375 134 108 135 369 136 367 137 1306 138 365 139 363 140 361 141 1284 142 1282 143 359 144 357 145 102 146 351 147 100 148 345 149 98 150 96 151 94 152 92 153 319 154 90 155 88 156 86 157 299 158 84 159 293 160 291 161 1026 162 1024 163 289 164 287 165 80 166 279 167 78 168 273 169 76 170 265 171 263 172 261 173 926 174 259 175 257 176 255 177 906 178 253 179 900 180 898 181 896 182 3139 183 894 184 892 185 890 186 3121 187 888 188 886 189 884 190 247 191 876 192 245 193 870 194 243 195 241 196 239 197 848 198 846 199 237 200 235 201 66 202 229 203 64 204 221 205 219 206 778 207 217 208 215 209 213 210 60 211 207 212 58 213 201 214 56 215 195 216 193 217 680 218 678 219 191 220 189 221 52 222 183 223 50 224 177 225 175 226 610 227 608 228 173 229 171 230 169 231 586 232 167 233 578 234 165 235 572 236 570 237 568 238 1999 239 566 240 564 241 562 242 1979 243 560 244 558 245 159 246 550 247 548 248 157 249 155 250 153 251 526 252 151 253 520 254 149 255 147 256 145 257 143 258 494 259 141 260 488 261 486 262 1711 263 484 264 482 265 480 266 137 267 472 268 135 269 133 270 131 271 452 272 129 273 127 274 125 275 123 276 424 277 121 278 418 279 119 280 410 281 408 282 1449 283 406 284 404 285 402 286 400 287 1419 288 398 289 396 290 113 291 390 292 111 293 382 294 380 295 378 296 1347 297 376 298 1341 299 374 300 372 301 370 302 1319 303 1317 304 368 305 1309 306 1307 307 4576 308 1305 309 1303 310 364 311 1297 312 1295 313 362 314 1287 315 1285 316 4500 317 1283 318 4492 319 1281 320 1279 321 358 322 1271 323 1269 324 356 325 354 326 352 327 1247 328 350 329 348 330 346 331 1225 332 1223 333 344 334 342 335 97 336 336 337 95 338 330 339 93 340 324 341 322 342 320 343 1129 344 318 345 316 346 89 347 310 348 87 349 304 350 302 351 300 352 1057 353 298 354 296 355 294 356 1037 357 292 358 1031 359 1029 360 1027 361 3602 362 1025 363 3596 364 1023 365 1021 366 288 367 1015 368 286 369 284 370 282 371 280 372 989 373 278 374 276 375 274 376 969 377 272 378 270 379 268 380 266 381 941 382 264 383 935 384 262 385 929 386 927 387 3252 388 3250 389 925 390 923 391 258 392 917 393 256 394 909 395 907 396 3178 397 3176 398 905 399 903 400 901 401 3156 402 899 403 3148 404 897 405 3142 406 3140 407 11065 408 11063 409 3138 410 3136 411 893 412 3130 413 891 414 3124 415 3122 416 10999 417 10997 418 3120 419 3118 420 887 421 3112 422 885 423 3106 424 883 425 881 426 879 427 877 428 3080 429 875 430 873 431 871 432 3060 433 869 434 867 435 865 436 242 437 857 438 240 439 851 440 849 441 2988 442 847 443 2982 444 845 445 843 446 841 447 236 448 835 449 234 450 232 451 230 452 813 453 228 454 226 455 224 456 222 457 787 458 220 459 781 460 779 461 2736 462 777 463 775 464 773 465 216 466 765 467 214 468 759 469 212 470 210 471 208 472 737 473 735 474 206 475 204 476 202 477 715 478 200 479 198 480 196 481 693 482 194 483 685 484 683 485 681 486 2392 487 679 488 2384 489 677 490 675 491 190 492 667 493 665 494 188 495 186 496 184 497 643 498 182 499 180 500 178 501 621 502 619 503 176 504 613 505 611 506 2150 507 609 508 2144 509 607 510 605 511 603 512 172 513 595 514 170 515 589 516 587 517 2070 518 585 519 583 520 581 521 579 522 2040 523 577 524 575 525 573 526 2018 527 571 528 2012 529 569 530 2004 531 2002 532 2000 533 7043 534 1998 535 1996 536 565 537 1990 538 563 539 1984 540 1982 541 1980 542 6971 543 1978 544 1976 545 559 546 1970 547 557 548 555 549 553 550 551 551 1944 552 549 553 1938 554 547 555 545 556 156 557 539 558 537 559 154 560 529 561 527 562 1860 563 525 564 523 565 521 566 1840 567 519 568 517 569 515 570 148 571 509 572 146 573 503 574 144 575 497 576 495 577 1744 578 1742 579 493 580 491 581 489 582 1720 583 487 584 1714 585 1712 586 6031 587 6029 588 1710 589 1708 590 483 591 1702 592 481 593 1696 594 479 595 477 596 475 597 473 598 1666 599 471 600 469 601 134 602 461 603 132 604 455 605 453 606 1600 607 1598 608 451 609 449 610 128 611 443 612 126 613 437 614 124 615 429 616 427 617 425 618 1504 619 423 620 421 621 419 622 1486 623 417 624 415 625 413 626 411 627 1458 628 409 629 1452 630 1450 631 5089 632 1448 633 1446 634 1444 635 405 636 1436 637 403 638 1430 639 401 640 1422 641 1420 642 4993 643 1418 644 1416 645 1414 646 397 647 1408 648 395 649 393 650 391 651 1388 652 389 653 387 654 385 655 383 656 1362 657 381 658 1356 659 379 660 1350 661 1348 662 4723 663 4721 664 1346 665 1344 666 1342 667 4699 668 1340 669 1338 670 373 671 1332 672 1330 673 371 674 1322 675 1320 676 4623 677 1318 678 4615 679 1316 680 1314 681 1312 682 1310 683 4585 684 1308 685 4579 686 4577 687 16122 688 4575 689 4573 690 1304 691 4565 692 4563 693 1302 694 1300 695 1298 696 4541 697 1296 698 4535 699 1294 700 1292 701 1290 702 1288 703 4509 704 1286 705 4503 706 4501 707 15862 708 4499 709 4497 710 4495 711 4493 712 15836 713 4491 714 4489 715 1280 716 4481 717 1278 718 1276 719 1274 720 1272 721 4451 722 1270 723 4445 724 1268 725 1266 726 355 727 1260 728 353 729 1252 730 1250 731 1248 732 4375 733 1246 734 1244 735 349 736 1238 737 347 738 1230 739 1228 740 1226 741 4297 742 1224 743 4291 744 1222 745 1220 746 343 747 1214 748 1212 749 341 750 339 751 337 752 1190 753 335 754 333 755 331 756 1168 757 1166 758 329 759 327 760 325 761 1146 762 323 763 1138 764 321 765 1132 766 1130 767 3969 768 3967 769 1128 770 1126 771 317 772 1120 773 315 774 313 775 311 776 1098 777 1096 778 309 779 307 780 305 781 1074 782 303 783 1068 784 301 785 1062 786 1060 787 1058 788 3715 789 1056 790 1054 791 297 792 1048 793 295 794 1042 795 1040 796 1038 797 3641 798 1036 799 1034 800 1032 801 3621 802 1030 803 3615 804 1028 805 3607 806 3605 807 3603 808 12696 809 3601 810 3599 811 3597 812 12674 813 3595 814 3593 815 3591 816 1022 817 3585 818 1020 819 1018 820 1016 821 3567 822 1014 823 1012 824 1010 825 285 826 1004 827 283 828 998 829 281 830 992 831 990 832 3471 833 3469 834 988 835 986 836 277 837 980 838 275 839 972 840 970 841 3405 842 968 843 966 844 964 845 271 846 958 847 269 848 950 849 267 850 944 851 942 852 3309 853 3307 854 940 855 938 856 936 857 3285 858 934 859 932 860 930 861 3263 862 3261 863 928 864 3255 865 3253 866 11456 867 3251 868 11450 869 3249 870 3247 871 3245 872 924 873 3237 874 922 875 920 876 918 877 3217 878 916 879 914 880 912 881 910 882 3187 883 908 884 3181 885 3179 886 11202 887 3177 888 11196 889 3175 890 3173 891 3171 892 904 893 3165 894 902 895 3159 896 3157 897 11122 898 3155 899 3153 900 3151 901 3149 902 11094 903 3147 904 3145 905 3143 906 11076 907 3141 908 11070 909 11068 910 11066 911 38915 912 11064 913 38909 914 11062 915 11060 916 3137 917 11054 918 11052 919 3135 920 3133 921 3131 922 11032 923 3129 924 3127 925 3125 926 11012 927 3123 928 11004 929 11002 930 11000 931 38681 932 10998 933 38675 934 10996 935 10994 936 3119 937 10986 938 10984 939 3117 940 3115 941 3113 942 10962 943 3111 944 3109 945 3107 946 10940 947 10938 948 3105 949 3103 950 882 951 3097 952 880 953 3091 954 878 955 3085 956 3083 957 3081 958 10842 959 3079 960 3077 961 874 962 3069 963 872 964 3063 965 3061 966 10774 967 10772 968 3059 969 3057 970 868 971 3049 972 866 973 3043 974 864 975 862 976 860 977 858 978 3017 979 856 980 854 981 852 982 2999 983 850 984 2993 985 2991 986 2989 987 10504 988 2987 989 2985 990 2983 991 10484 992 2981 993 2979 994 2977 995 844 996 2969 997 842 998 2963 999 840 1000 838 1001 836 1002 2941 1003 834 1004 832 1005 830 1006 233 1007 824 1008 231 1009 816 1010 814 1011 2865 1012 812 1013 810 1014 808 1015 227 1016 802 1017 225 1018 796 1019 223 1020 790 1021 788 1022 2769 1023 2767 1024 786 1025 784 1026 782 1027 2745 1028 780 1029 2739 1030 2737 1031 9628 1032 9626 1033 2735 1034 2733 1035 776 1036 2727 1037 774 1038 2719 1039 772 1040 770 1041 768 1042 766 1043 2689 1044 764 1045 762 1046 760 1047 2667 1048 758 1049 756 1050 211 1051 748 1052 746 1053 209 1054 740 1055 738 1056 2591 1057 736 1058 2585 1059 734 1060 732 1061 730 1062 205 1063 724 1064 203 1065 718 1066 716 1067 2511 1068 714 1069 712 1070 710 1071 199 1072 702 1073 197 1074 696 1075 694 1076 2439 1077 692 1078 690 1079 688 1080 686 1081 2409 1082 684 1083 2403 1084 682 1085 2395 1086 2393 1087 8424 1088 2391 1089 2389 1090 2387 1091 2385 1092 8394 1093 2383 1094 2381 1095 676 1096 2375 1097 674 1098 672 1099 670 1100 668 1101 2349 1102 666 1103 2343 1104 664 1105 662 1106 187 1107 656 1108 654 1109 185 1110 646 1111 644 1112 2265 1113 642 1114 640 1115 181 1116 634 1117 632 1118 179 1119 624 1120 622 1121 2189 1122 620 1123 2181 1124 618 1125 616 1126 614 1127 2161 1128 2159 1129 612 1130 2153 1131 2151 1132 7566 1133 2149 1134 2147 1135 2145 1136 7544 1137 7542 1138 2143 1139 2141 1140 606 1141 2135 1142 604 1143 2129 1144 602 1145 600 1146 598 1147 596 1148 2101 1149 594 1150 592 1151 590 1152 2081 1153 588 1154 2075 1155 2073 1156 2071 1157 7278 1158 2069 1159 2067 1160 584 1161 2059 1162 582 1163 2053 1164 580 1165 2045 1166 2043 1167 2041 1168 7174 1169 2039 1170 2037 1171 576 1172 2031 1173 574 1174 2023 1175 2021 1176 2019 1177 7102 1178 2017 1179 2015 1180 2013 1181 7084 1182 2011 1183 2009 1184 2007 1185 2005 1186 7058 1187 2003 1188 7052 1189 2001 1190 7046 1191 7044 1192 24775 1193 24773 1194 7042 1195 7040 1196 1997 1197 7034 1198 1995 1199 1993 1200 1991 1201 7012 1202 7010 1203 1989 1204 1987 1205 1985 1206 6988 1207 1983 1208 6980 1209 1981 1210 6974 1211 6972 1212 24529 1213 24527 1214 6970 1215 6968 1216 1977 1217 6962 1218 1975 1219 1973 1220 1971 1221 6940 1222 6938 1223 1969 1224 1967 1225 556 1226 1961 1227 554 1228 1955 1229 552 1230 1949 1231 1947 1232 1945 1233 6840 1234 1943 1235 1941 1236 1939 1237 6818 1238 1937 1239 1935 1240 1933 1241 546 1242 1925 1243 544 1244 542 1245 540 1246 1903 1247 538 1248 1897 1249 536 1250 534 1251 532 1252 530 1253 1869 1254 528 1255 1863 1256 1861 1257 6550 1258 1859 1259 1857 1260 1855 1261 524 1262 1849 1263 522 1264 1843 1265 1841 1266 6480 1267 1839 1268 1837 1269 1835 1270 518 1271 1827 1272 516 1273 1821 1274 514 1275 512 1276 510 1277 1799 1278 1797 1279 508 1280 506 1281 504 1282 1777 1283 502 1284 500 1285 498 1286 1757 1287 496 1288 1749 1289 1747 1290 1745 1291 6148 1292 1743 1293 6140 1294 1741 1295 1739 1296 492 1297 1731 1298 1729 1299 490 1300 1723 1301 1721 1302 6066 1303 1719 1304 1717 1305 1715 1306 6044 1307 6042 1308 1713 1309 6034 1310 6032 1311 21201 1312 6030 1313 21195 1314 6028 1315 6026 1316 6024 1317 1709 1318 6016 1319 1707 1320 1705 1321 1703 1322 5996 1323 1701 1324 1699 1325 1697 1326 5976 1327 5974 1328 1695 1329 1693 1330 478 1331 1685 1332 476 1333 1679 1334 474 1335 1671 1336 1669 1337 1667 1338 5874 1339 1665 1340 1663 1341 470 1342 1657 1343 468 1344 466 1345 464 1346 462 1347 1631 1348 460 1349 458 1350 456 1351 1611 1352 454 1353 1605 1354 1603 1355 1601 1356 5640 1357 1599 1358 5634 1359 1597 1360 1595 1361 450 1362 1589 1363 1587 1364 448 1365 446 1366 444 1367 1565 1368 442 1369 440 1370 438 1371 1545 1372 436 1373 434 1374 432 1375 430 1376 1519 1377 428 1378 1513 1379 426 1380 1507 1381 1505 1382 5296 1383 5294 1384 1503 1385 1501 1386 422 1387 1495 1388 420 1389 1489 1390 1487 1391 5226 1392 5224 1393 1485 1394 1483 1395 416 1396 1477 1397 414 1398 1469 1399 412 1400 1463 1401 1461 1402 1459 1403 5120 1404 1457 1405 1455 1406 1453 1407 5098 1408 1451 1409 5092 1410 5090 1411 17915 1412 17913 1413 5088 1414 5086 1415 1447 1416 5080 1417 1445 1418 5074 1419 1443 1420 1441 1421 1439 1422 1437 1423 5046 1424 1435 1425 1433 1426 1431 1427 5028 1428 1429 1429 1427 1430 1425 1431 1423 1432 5002 1433 1421 1434 4996 1435 4994 1436 17559 1437 4992 1438 4990 1439 4988 1440 1417 1441 4980 1442 1415 1443 4974 1444 1413 1445 1411 1446 1409 1447 4954 1448 1407 1449 1405 1450 1403 1451 394 1452 1397 1453 392 1454 1391 1455 1389 1456 4878 1457 1387 1458 1385 1459 1383 1460 388 1461 1377 1462 386 1463 1371 1464 384 1465 1365 1466 1363 1467 4782 1468 4780 1469 1361 1470 1359 1471 1357 1472 4758 1473 1355 1474 1353 1475 1351 1476 4736 1477 4734 1478 1349 1479 4726 1480 4724 1481 16635 1482 4722 1483 16627 1484 4720 1485 4718 1486 1345 1487 4710 1488 4708 1489 1343 1490 4702 1491 4700 1492 16549 1493 4698 1494 4696 1495 1339 1496 4688 1497 4686 1498 1337 1499 1335 1500 1333 1501 4664 1502 1331 1503 4658 1504 1329 1505 1327 1506 1325 1507 1323 1508 4632 1509 1321 1510 4626 1511 4624 1512 16283 1513 4622 1514 4620 1515 4618 1516 4616 1517 16257 1518 4614 1519 4612 1520 1315 1521 4604 1522 1313 1523 4598 1524 1311 1525 4590 1526 4588 1527 4586 1528 16155 1529 4584 1530 4582 1531 4580 1532 16135 1533 4578 1534 16127 1535 16125 1536 16123 1537 56712 1538 16121 1539 16119 1540 4574 1541 16113 1542 4572 1543 4570 1544 4568 1545 4566 1546 16087 1547 4564 1548 16081 1549 4562 1550 4560 1551 1301 1552 4554 1553 4552 1554 1299 1555 4544 1556 4542 1557 16005 1558 4540 1559 4538 1560 4536 1561 15983 1562 15981 1563 4534 1564 4532 1565 1293 1566 4526 1567 1291 1568 4518 1569 1289 1570 4512 1571 4510 1572 15895 1573 15893 1574 4508 1575 4506 1576 4504 1577 15871 1578 4502 1579 15865 1580 15863 1581 55780 1582 55778 1583 15861 1584 15859 1585 4498 1586 15853 1587 4496 1588 15847 1589 4494 1590 15841 1591 15839 1592 15837 1593 55680 1594 15835 1595 15833 1596 4490 1597 15825 1598 4488 1599 4486 1600 4484 1601 4482 1602 15795 1603 4480 1604 4478 1605 1277 1606 4470 1607 1275 1608 4464 1609 1273 1610 4456 1611 4454 1612 4452 1613 15699 1614 4450 1615 4448 1616 4446 1617 15679 1618 4444 1619 4442 1620 4440 1621 1267 1622 4434 1623 1265 1624 1263 1625 1261 1626 4416 1627 1259 1628 1257 1629 1255 1630 1253 1631 4390 1632 1251 1633 4384 1634 1249 1635 4378 1636 4376 1637 15421 1638 15419 1639 4374 1640 4372 1641 1245 1642 4366 1643 1243 1644 1241 1645 1239 1646 4344 1647 1237 1648 1235 1649 1233 1650 1231 1651 4314 1652 1229 1653 4306 1654 1227 1655 4300 1656 4298 1657 15153 1658 15151 1659 4296 1660 4294 1661 4292 1662 15131 1663 4290 1664 4288 1665 1221 1666 4282 1667 4280 1668 1219 1669 1217 1670 1215 1671 4258 1672 1213 1673 4252 1674 1211 1675 1209 1676 1207 1677 340 1678 1199 1679 338 1680 1193 1681 1191 1682 4182 1683 1189 1684 1187 1685 334 1686 1179 1687 1177 1688 332 1689 1171 1690 1169 1691 4102 1692 1167 1693 4096 1694 1165 1695 1163 1696 1161 1697 328 1698 1155 1699 326 1700 1149 1701 1147 1702 4024 1703 1145 1704 1143 1705 1141 1706 1139 1707 3998 1708 1137 1709 1135 1710 1133 1711 3980 1712 1131 1713 3974 1714 3972 1715 3970 1716 13997 1717 3968 1718 13991 1719 3966 1720 3964 1721 1127 1722 3958 1723 3956 1724 1125 1725 1123 1726 1121 1727 3934 1728 1119 1729 1117 1730 314 1731 1111 1732 312 1733 1103 1734 1101 1735 1099 1736 3864 1737 1097 1738 3858 1739 1095 1740 1093 1741 308 1742 1085 1743 1083 1744 306 1745 1077 1746 1075 1747 3778 1748 1073 1749 1071 1750 1069 1751 3758 1752 3756 1753 1067 1754 1065 1755 1063 1756 3734 1757 1061 1758 3726 1759 1059 1760 3720 1761 3718 1762 3716 1763 13093 1764 3714 1765 3712 1766 1055 1767 3704 1768 1053 1769 1051 1770 1049 1771 3684 1772 3682 1773 1047 1774 1045 1775 1043 1776 3660 1777 1041 1778 3654 1779 1039 1780 3646 1781 3644 1782 3642 1783 12835 1784 3640 1785 3638 1786 1035 1787 3632 1788 1033 1789 3626 1790 3624 1791 3622 1792 12763 1793 3620 1794 3618 1795 3616 1796 12743 1797 3614 1798 3612 1799 3610 1800 3608 1801 12713 1802 3606 1803 12707 1804 3604 1805 12699 1806 12697 1807 44662 1808 12695 1809 12693 1810 12691 1811 3600 1812 12685 1813 3598 1814 12677 1815 12675 1816 44580 1817 12673 1818 12671 1819 12669 1820 3594 1821 12663 1822 3592 1823 12657 1824 3590 1825 3588 1826 3586 1827 12635 1828 12633 1829 3584 1830 3582 1831 1019 1832 3576 1833 1017 1834 3570 1835 3568 1836 12567 1837 12565 1838 3566 1839 3564 1840 1013 1841 3558 1842 1011 1843 3550 1844 1009 1845 1007 1846 1005 1847 3528 1848 3526 1849 1003 1850 1001 1851 999 1852 3504 1853 997 1854 995 1855 993 1856 3482 1857 3480 1858 991 1859 3474 1860 3472 1861 12237 1862 3470 1863 12231 1864 3468 1865 3466 1866 3464 1867 987 1868 3458 1869 985 1870 983 1871 981 1872 3440 1873 979 1874 977 1875 975 1876 973 1877 3414 1878 971 1879 3408 1880 3406 1881 11995 1882 3404 1883 3402 1884 3400 1885 967 1886 3392 1887 965 1888 3386 1889 963 1890 961 1891 959 1892 3366 1893 957 1894 955 1895 953 1896 951 1897 3340 1898 949 1899 947 1900 945 1901 3320 1902 943 1903 3314 1904 3312 1905 3310 1906 11653 1907 3308 1908 11647 1909 3306 1910 3304 1911 939 1912 3298 1913 3296 1914 937 1915 3288 1916 3286 1917 11573 1918 3284 1919 3282 1920 933 1921 3276 1922 3274 1923 931 1924 3266 1925 3264 1926 11495 1927 3262 1928 11487 1929 3260 1930 3258 1931 3256 1932 11467 1933 11465 1934 3254 1935 11459 1936 11457 1937 40304 1938 11455 1939 11453 1940 11451 1941 40282 1942 40280 1943 11449 1944 11447 1945 3248 1946 11441 1947 3246 1948 11435 1949 3244 1950 3242 1951 3240 1952 3238 1953 11409 1954 3236 1955 3234 1956 921 1957 3228 1958 919 1959 3222 1960 3220 1961 3218 1962 11335 1963 3216 1964 3214 1965 915 1966 3206 1967 913 1968 3200 1969 911 1970 3192 1971 3190 1972 3188 1973 11237 1974 3186 1975 3184 1976 3182 1977 11215 1978 3180 1979 11207 1980 11205 1981 11203 1982 39408 1983 11201 1984 11199 1985 11197 1986 39390 1987 11195 1988 11193 1989 11191 1990 3174 1991 11183 1992 3172 1993 11177 1994 3170 1995 3168 1996 3166 1997 11155 1998 11153 1999 3164 2000 3162