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