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