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