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