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