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