0 0 1 0 2 1 3 2 4 2 5 3 6 4 7 4 8 5 9 6 10 6 11 7 12 8 13 8 14 9 15 10 16 10 17 11 18 12 19 12 20 13 21 14 22 14 23 15 24 16 25 16 26 17 27 18 28 18 29 19 30 20 31 20 32 21 33 22 34 22 35 23 36 24 37 24 38 25 39 26 40 26 41 27 42 28 43 28 44 29 45 30 46 30 47 31 48 32 49 32 50 33 51 34 52 34 53 35 54 36 55 36 56 37 57 38 58 38 59 39 60 40 61 40 62 41 63 42 64 42 65 43 66 44 67 44 68 45 69 46 70 46 71 47 72 48 73 48 74 49 75 50 76 50 77 51 78 52 79 52 80 53 81 54 82 54 83 55 84 56 85 56 86 57 87 58 88 58 89 59 90 60 91 60 92 61 93 62 94 62 95 63 96 64 97 64 98 65 99 66 100 66 101 67 102 68 103 68 104 69 105 70 106 70 107 71 108 72 109 72 110 73 111 74 112 74 113 75 114 76 115 76 116 77 117 78 118 78 119 79 120 80 121 80 122 81 123 82 124 82 125 83 126 84 127 84 128 85 129 86 130 86 131 87 132 88 133 88 134 89 135 90 136 90 137 91 138 92 139 92 140 93 141 94 142 94 143 95 144 96 145 96 146 97 147 98 148 98 149 99 150 100 151 100 152 101 153 102 154 102 155 103 156 104 157 104 158 105 159 106 160 106 161 107 162 108 163 108 164 109 165 110 166 110 167 111 168 112 169 112 170 113 171 114 172 114 173 115 174 116 175 116 176 117 177 118 178 118 179 119 180 120 181 120 182 121 183 122 184 122 185 123 186 124 187 124 188 125 189 126 190 126 191 127 192 128 193 128 194 129 195 130 196 130 197 131 198 132 199 132 200 133 201 134 202 134 203 135 204 136 205 136 206 137 207 138 208 138 209 139 210 140 211 140 212 141 213 142 214 142 215 143 216 144 217 144 218 145 219 146 220 146 221 147 222 148 223 148 224 149 225 150 226 150 227 151 228 152 229 152 230 153 231 154 232 154 233 155 234 156 235 156 236 157 237 158 238 158 239 159 240 160 241 160 242 161 243 162 244 162 245 163 246 164 247 164 248 165 249 166 250 166 251 167 252 168 253 168 254 169 255 170 256 170 257 171 258 172 259 172 260 173 261 174 262 174 263 175 264 176 265 176 266 177 267 178 268 178 269 179 270 180 271 180 272 181 273 182 274 182 275 183 276 184 277 184 278 185 279 186 280 186 281 187 282 188 283 188 284 189 285 190 286 190 287 191 288 192 289 192 290 193 291 194 292 194 293 195 294 196 295 196 296 197 297 198 298 198 299 199 300 200 301 200 302 201 303 202 304 202 305 203 306 204 307 204 308 205 309 206 310 206 311 207 312 208 313 208 314 209 315 210 316 210 317 211 318 212 319 212 320 213 321 214 322 214 323 215 324 216 325 216 326 217 327 218 328 218 329 219 330 220 331 220 332 221 333 222 334 222 335 223 336 224 337 224 338 225 339 226 340 226 341 227 342 228 343 228 344 229 345 230 346 230 347 231 348 232 349 232 350 233 351 234 352 234 353 235 354 236 355 236 356 237 357 238 358 238 359 239 360 240 361 240 362 241 363 242 364 242 365 243 366 244 367 244 368 245 369 246 370 246 371 247 372 248 373 248 374 249 375 250 376 250 377 251 378 252 379 252 380 253 381 254 382 254 383 255 384 256 385 256 386 257 387 258 388 258 389 259 390 260 391 260 392 261 393 262 394 262 395 263 396 264 397 264 398 265 399 266 400 266 401 267 402 268 403 268 404 269 405 270 406 270 407 271 408 272 409 272 410 273 411 274 412 274 413 275 414 276 415 276 416 277 417 278 418 278 419 279 420 280 421 280 422 281 423 282 424 282 425 283 426 284 427 284 428 285 429 286 430 286 431 287 432 288 433 288 434 289 435 290 436 290 437 291 438 292 439 292 440 293 441 294 442 294 443 295 444 296 445 296 446 297 447 298 448 298 449 299 450 300 451 300 452 301 453 302 454 302 455 303 456 304 457 304 458 305 459 306 460 306 461 307 462 308 463 308 464 309 465 310 466 310 467 311 468 312 469 312 470 313 471 314 472 314 473 315 474 316 475 316 476 317 477 318 478 318 479 319 480 320 481 320 482 321 483 322 484 322 485 323 486 324 487 324 488 325 489 326 490 326 491 327 492 328 493 328 494 329 495 330 496 330 497 331 498 332 499 332 500 333 501 334 502 334 503 335 504 336 505 336 506 337 507 338 508 338 509 339 510 340 511 340 512 341 513 342 514 342 515 343 516 344 517 344 518 345 519 346 520 346 521 347 522 348 523 348 524 349 525 350 526 350 527 351 528 352 529 352 530 353 531 354 532 354 533 355 534 356 535 356 536 357 537 358 538 358 539 359 540 360 541 360 542 361 543 362 544 362 545 363 546 364 547 364 548 365 549 366 550 366 551 367 552 368 553 368 554 369 555 370 556 370 557 371 558 372 559 372 560 373 561 374 562 374 563 375 564 376 565 376 566 377 567 378 568 378 569 379 570 380 571 380 572 381 573 382 574 382 575 383 576 384 577 384 578 385 579 386 580 386 581 387 582 388 583 388 584 389 585 390 586 390 587 391 588 392 589 392 590 393 591 394 592 394 593 395 594 396 595 396 596 397 597 398 598 398 599 399 600 400 601 400 602 401 603 402 604 402 605 403 606 404 607 404 608 405 609 406 610 406 611 407 612 408 613 408 614 409 615 410 616 410 617 411 618 412 619 412 620 413 621 414 622 414 623 415 624 416 625 416 626 417 627 418 628 418 629 419 630 420 631 420 632 421 633 422 634 422 635 423 636 424 637 424 638 425 639 426 640 426 641 427 642 428 643 428 644 429 645 430 646 430 647 431 648 432 649 432 650 433 651 434 652 434 653 435 654 436 655 436 656 437 657 438 658 438 659 439 660 440 661 440 662 441 663 442 664 442 665 443 666 444 667 444 668 445 669 446 670 446 671 447 672 448 673 448 674 449 675 450 676 450 677 451 678 452 679 452 680 453 681 454 682 454 683 455 684 456 685 456 686 457 687 458 688 458 689 459 690 460 691 460 692 461 693 462 694 462 695 463 696 464 697 464 698 465 699 466 700 466 701 467 702 468 703 468 704 469 705 470 706 470 707 471 708 472 709 472 710 473 711 474 712 474 713 475 714 476 715 476 716 477 717 478 718 478 719 479 720 480 721 480 722 481 723 482 724 482 725 483 726 484 727 484 728 485 729 486 730 486 731 487 732 488 733 488 734 489 735 490 736 490 737 491 738 492 739 492 740 493 741 494 742 494 743 495 744 496 745 496 746 497 747 498 748 498 749 499 750 500 751 500 752 501 753 502 754 502 755 503 756 504 757 504 758 505 759 506 760 506 761 507 762 508 763 508 764 509 765 510 766 510 767 511 768 512 769 512 770 513 771 514 772 514 773 515 774 516 775 516 776 517 777 518 778 518 779 519 780 520 781 520 782 521 783 522 784 522 785 523 786 524 787 524 788 525 789 526 790 526 791 527 792 528 793 528 794 529 795 530 796 530 797 531 798 532 799 532 800 533 801 534 802 534 803 535 804 536 805 536 806 537 807 538 808 538 809 539 810 540 811 540 812 541 813 542 814 542 815 543 816 544 817 544 818 545 819 546 820 546 821 547 822 548 823 548 824 549 825 550 826 550 827 551 828 552 829 552 830 553 831 554 832 554 833 555 834 556 835 556 836 557 837 558 838 558 839 559 840 560 841 560 842 561 843 562 844 562 845 563 846 564 847 564 848 565 849 566 850 566 851 567 852 568 853 568 854 569 855 570 856 570 857 571 858 572 859 572 860 573 861 574 862 574 863 575 864 576 865 576 866 577 867 578 868 578 869 579 870 580 871 580 872 581 873 582 874 582 875 583 876 584 877 584 878 585 879 586 880 586 881 587 882 588 883 588 884 589 885 590 886 590 887 591 888 592 889 592 890 593 891 594 892 594 893 595 894 596 895 596 896 597 897 598 898 598 899 599 900 600 901 600 902 601 903 602 904 602 905 603 906 604 907 604 908 605 909 606 910 606 911 607 912 608 913 608 914 609 915 610 916 610 917 611 918 612 919 612 920 613 921 614 922 614 923 615 924 616 925 616 926 617 927 618 928 618 929 619 930 620 931 620 932 621 933 622 934 622 935 623 936 624 937 624 938 625 939 626 940 626 941 627 942 628 943 628 944 629 945 630 946 630 947 631 948 632 949 632 950 633 951 634 952 634 953 635 954 636 955 636 956 637 957 638 958 638 959 639 960 640 961 640 962 641 963 642 964 642 965 643 966 644 967 644 968 645 969 646 970 646 971 647 972 648 973 648 974 649 975 650 976 650 977 651 978 652 979 652 980 653 981 654 982 654 983 655 984 656 985 656 986 657 987 658 988 658 989 659 990 660 991 660 992 661 993 662 994 662 995 663 996 664 997 664 998 665 999 666 1000 666 1001 667 1002 668 1003 668 1004 669 1005 670 1006 670 1007 671 1008 672 1009 672 1010 673 1011 674 1012 674 1013 675 1014 676 1015 676 1016 677 1017 678 1018 678 1019 679 1020 680 1021 680 1022 681 1023 682 1024 682 1025 683 1026 684 1027 684 1028 685 1029 686 1030 686 1031 687 1032 688 1033 688 1034 689 1035 690 1036 690 1037 691 1038 692 1039 692 1040 693 1041 694 1042 694 1043 695 1044 696 1045 696 1046 697 1047 698 1048 698 1049 699 1050 700 1051 700 1052 701 1053 702 1054 702 1055 703 1056 704 1057 704 1058 705 1059 706 1060 706 1061 707 1062 708 1063 708 1064 709 1065 710 1066 710 1067 711 1068 712 1069 712 1070 713 1071 714 1072 714 1073 715 1074 716 1075 716 1076 717 1077 718 1078 718 1079 719 1080 720 1081 720 1082 721 1083 722 1084 722 1085 723 1086 724 1087 724 1088 725 1089 726 1090 726 1091 727 1092 728 1093 728 1094 729 1095 730 1096 730 1097 731 1098 732 1099 732 1100 733 1101 734 1102 734 1103 735 1104 736 1105 736 1106 737 1107 738 1108 738 1109 739 1110 740 1111 740 1112 741 1113 742 1114 742 1115 743 1116 744 1117 744 1118 745 1119 746 1120 746 1121 747 1122 748 1123 748 1124 749 1125 750 1126 750 1127 751 1128 752 1129 752 1130 753 1131 754 1132 754 1133 755 1134 756 1135 756 1136 757 1137 758 1138 758 1139 759 1140 760 1141 760 1142 761 1143 762 1144 762 1145 763 1146 764 1147 764 1148 765 1149 766 1150 766 1151 767 1152 768 1153 768 1154 769 1155 770 1156 770 1157 771 1158 772 1159 772 1160 773 1161 774 1162 774 1163 775 1164 776 1165 776 1166 777 1167 778 1168 778 1169 779 1170 780 1171 780 1172 781 1173 782 1174 782 1175 783 1176 784 1177 784 1178 785 1179 786 1180 786 1181 787 1182 788 1183 788 1184 789 1185 790 1186 790 1187 791 1188 792 1189 792 1190 793 1191 794 1192 794 1193 795 1194 796 1195 796 1196 797 1197 798 1198 798 1199 799 1200 800 1201 800 1202 801 1203 802 1204 802 1205 803 1206 804 1207 804 1208 805 1209 806 1210 806 1211 807 1212 808 1213 808 1214 809 1215 810 1216 810 1217 811 1218 812 1219 812 1220 813 1221 814 1222 814 1223 815 1224 816 1225 816 1226 817 1227 818 1228 818 1229 819 1230 820 1231 820 1232 821 1233 822 1234 822 1235 823 1236 824 1237 824 1238 825 1239 826 1240 826 1241 827 1242 828 1243 828 1244 829 1245 830 1246 830 1247 831 1248 832 1249 832 1250 833 1251 834 1252 834 1253 835 1254 836 1255 836 1256 837 1257 838 1258 838 1259 839 1260 840 1261 840 1262 841 1263 842 1264 842 1265 843 1266 844 1267 844 1268 845 1269 846 1270 846 1271 847 1272 848 1273 848 1274 849 1275 850 1276 850 1277 851 1278 852 1279 852 1280 853 1281 854 1282 854 1283 855 1284 856 1285 856 1286 857 1287 858 1288 858 1289 859 1290 860 1291 860 1292 861 1293 862 1294 862 1295 863 1296 864 1297 864 1298 865 1299 866 1300 866 1301 867 1302 868 1303 868 1304 869 1305 870 1306 870 1307 871 1308 872 1309 872 1310 873 1311 874 1312 874 1313 875 1314 876 1315 876 1316 877 1317 878 1318 878 1319 879 1320 880 1321 880 1322 881 1323 882 1324 882 1325 883 1326 884 1327 884 1328 885 1329 886 1330 886 1331 887 1332 888 1333 888 1334 889 1335 890 1336 890 1337 891 1338 892 1339 892 1340 893 1341 894 1342 894 1343 895 1344 896 1345 896 1346 897 1347 898 1348 898 1349 899 1350 900 1351 900 1352 901 1353 902 1354 902 1355 903 1356 904 1357 904 1358 905 1359 906 1360 906 1361 907 1362 908 1363 908 1364 909 1365 910 1366 910 1367 911 1368 912 1369 912 1370 913 1371 914 1372 914 1373 915 1374 916 1375 916 1376 917 1377 918 1378 918 1379 919 1380 920 1381 920 1382 921 1383 922 1384 922 1385 923 1386 924 1387 924 1388 925 1389 926 1390 926 1391 927 1392 928 1393 928 1394 929 1395 930 1396 930 1397 931 1398 932 1399 932 1400 933 1401 934 1402 934 1403 935 1404 936 1405 936 1406 937 1407 938 1408 938 1409 939 1410 940 1411 940 1412 941 1413 942 1414 942 1415 943 1416 944 1417 944 1418 945 1419 946 1420 946 1421 947 1422 948 1423 948 1424 949 1425 950 1426 950 1427 951 1428 952 1429 952 1430 953 1431 954 1432 954 1433 955 1434 956 1435 956 1436 957 1437 958 1438 958 1439 959 1440 960 1441 960 1442 961 1443 962 1444 962 1445 963 1446 964 1447 964 1448 965 1449 966 1450 966 1451 967 1452 968 1453 968 1454 969 1455 970 1456 970 1457 971 1458 972 1459 972 1460 973 1461 974 1462 974 1463 975 1464 976 1465 976 1466 977 1467 978 1468 978 1469 979 1470 980 1471 980 1472 981 1473 982 1474 982 1475 983 1476 984 1477 984 1478 985 1479 986 1480 986 1481 987 1482 988 1483 988 1484 989 1485 990 1486 990 1487 991 1488 992 1489 992 1490 993 1491 994 1492 994 1493 995 1494 996 1495 996 1496 997 1497 998 1498 998 1499 999 1500 1000 1501 1000 1502 1001 1503 1002 1504 1002 1505 1003 1506 1004 1507 1004 1508 1005 1509 1006 1510 1006 1511 1007 1512 1008 1513 1008 1514 1009 1515 1010 1516 1010 1517 1011 1518 1012 1519 1012 1520 1013 1521 1014 1522 1014 1523 1015 1524 1016 1525 1016 1526 1017 1527 1018 1528 1018 1529 1019 1530 1020 1531 1020 1532 1021 1533 1022 1534 1022 1535 1023 1536 1024 1537 1024 1538 1025 1539 1026 1540 1026 1541 1027 1542 1028 1543 1028 1544 1029 1545 1030 1546 1030 1547 1031 1548 1032 1549 1032 1550 1033 1551 1034 1552 1034 1553 1035 1554 1036 1555 1036 1556 1037 1557 1038 1558 1038 1559 1039 1560 1040 1561 1040 1562 1041 1563 1042 1564 1042 1565 1043 1566 1044 1567 1044 1568 1045 1569 1046 1570 1046 1571 1047 1572 1048 1573 1048 1574 1049 1575 1050 1576 1050 1577 1051 1578 1052 1579 1052 1580 1053 1581 1054 1582 1054 1583 1055 1584 1056 1585 1056 1586 1057 1587 1058 1588 1058 1589 1059 1590 1060 1591 1060 1592 1061 1593 1062 1594 1062 1595 1063 1596 1064 1597 1064 1598 1065 1599 1066 1600 1066 1601 1067 1602 1068 1603 1068 1604 1069 1605 1070 1606 1070 1607 1071 1608 1072 1609 1072 1610 1073 1611 1074 1612 1074 1613 1075 1614 1076 1615 1076 1616 1077 1617 1078 1618 1078 1619 1079 1620 1080 1621 1080 1622 1081 1623 1082 1624 1082 1625 1083 1626 1084 1627 1084 1628 1085 1629 1086 1630 1086 1631 1087 1632 1088 1633 1088 1634 1089 1635 1090 1636 1090 1637 1091 1638 1092 1639 1092 1640 1093 1641 1094 1642 1094 1643 1095 1644 1096 1645 1096 1646 1097 1647 1098 1648 1098 1649 1099 1650 1100 1651 1100 1652 1101 1653 1102 1654 1102 1655 1103 1656 1104 1657 1104 1658 1105 1659 1106 1660 1106 1661 1107 1662 1108 1663 1108 1664 1109 1665 1110 1666 1110 1667 1111 1668 1112 1669 1112 1670 1113 1671 1114 1672 1114 1673 1115 1674 1116 1675 1116 1676 1117 1677 1118 1678 1118 1679 1119 1680 1120 1681 1120 1682 1121 1683 1122 1684 1122 1685 1123 1686 1124 1687 1124 1688 1125 1689 1126 1690 1126 1691 1127 1692 1128 1693 1128 1694 1129 1695 1130 1696 1130 1697 1131 1698 1132 1699 1132 1700 1133 1701 1134 1702 1134 1703 1135 1704 1136 1705 1136 1706 1137 1707 1138 1708 1138 1709 1139 1710 1140 1711 1140 1712 1141 1713 1142 1714 1142 1715 1143 1716 1144 1717 1144 1718 1145 1719 1146 1720 1146 1721 1147 1722 1148 1723 1148 1724 1149 1725 1150 1726 1150 1727 1151 1728 1152 1729 1152 1730 1153 1731 1154 1732 1154 1733 1155 1734 1156 1735 1156 1736 1157 1737 1158 1738 1158 1739 1159 1740 1160 1741 1160 1742 1161 1743 1162 1744 1162 1745 1163 1746 1164 1747 1164 1748 1165 1749 1166 1750 1166 1751 1167 1752 1168 1753 1168 1754 1169 1755 1170 1756 1170 1757 1171 1758 1172 1759 1172 1760 1173 1761 1174 1762 1174 1763 1175 1764 1176 1765 1176 1766 1177 1767 1178 1768 1178 1769 1179 1770 1180 1771 1180 1772 1181 1773 1182 1774 1182 1775 1183 1776 1184 1777 1184 1778 1185 1779 1186 1780 1186 1781 1187 1782 1188 1783 1188 1784 1189 1785 1190 1786 1190 1787 1191 1788 1192 1789 1192 1790 1193 1791 1194 1792 1194 1793 1195 1794 1196 1795 1196 1796 1197 1797 1198 1798 1198 1799 1199 1800 1200 1801 1200 1802 1201 1803 1202 1804 1202 1805 1203 1806 1204 1807 1204 1808 1205 1809 1206 1810 1206 1811 1207 1812 1208 1813 1208 1814 1209 1815 1210 1816 1210 1817 1211 1818 1212 1819 1212 1820 1213 1821 1214 1822 1214 1823 1215 1824 1216 1825 1216 1826 1217 1827 1218 1828 1218 1829 1219 1830 1220 1831 1220 1832 1221 1833 1222 1834 1222 1835 1223 1836 1224 1837 1224 1838 1225 1839 1226 1840 1226 1841 1227 1842 1228 1843 1228 1844 1229 1845 1230 1846 1230 1847 1231 1848 1232 1849 1232 1850 1233 1851 1234 1852 1234 1853 1235 1854 1236 1855 1236 1856 1237 1857 1238 1858 1238 1859 1239 1860 1240 1861 1240 1862 1241 1863 1242 1864 1242 1865 1243 1866 1244 1867 1244 1868 1245 1869 1246 1870 1246 1871 1247 1872 1248 1873 1248 1874 1249 1875 1250 1876 1250 1877 1251 1878 1252 1879 1252 1880 1253 1881 1254 1882 1254 1883 1255 1884 1256 1885 1256 1886 1257 1887 1258 1888 1258 1889 1259 1890 1260 1891 1260 1892 1261 1893 1262 1894 1262 1895 1263 1896 1264 1897 1264 1898 1265 1899 1266 1900 1266 1901 1267 1902 1268 1903 1268 1904 1269 1905 1270 1906 1270 1907 1271 1908 1272 1909 1272 1910 1273 1911 1274 1912 1274 1913 1275 1914 1276 1915 1276 1916 1277 1917 1278 1918 1278 1919 1279 1920 1280 1921 1280 1922 1281 1923 1282 1924 1282 1925 1283 1926 1284 1927 1284 1928 1285 1929 1286 1930 1286 1931 1287 1932 1288 1933 1288 1934 1289 1935 1290 1936 1290 1937 1291 1938 1292 1939 1292 1940 1293 1941 1294 1942 1294 1943 1295 1944 1296 1945 1296 1946 1297 1947 1298 1948 1298 1949 1299 1950 1300 1951 1300 1952 1301 1953 1302 1954 1302 1955 1303 1956 1304 1957 1304 1958 1305 1959 1306 1960 1306 1961 1307 1962 1308 1963 1308 1964 1309 1965 1310 1966 1310 1967 1311 1968 1312 1969 1312 1970 1313 1971 1314 1972 1314 1973 1315 1974 1316 1975 1316 1976 1317 1977 1318 1978 1318 1979 1319 1980 1320 1981 1320 1982 1321 1983 1322 1984 1322 1985 1323 1986 1324 1987 1324 1988 1325 1989 1326 1990 1326 1991 1327 1992 1328 1993 1328 1994 1329 1995 1330 1996 1330 1997 1331 1998 1332 1999 1332 2000 1333