#include #include using namespace std; const int P=1000000007; int val[]={ 0, 1, 2, 2, 2, 4, 5, 4, 8, 8, 7, 11, 8, 13, 4, 11, 12, 8, 12, 2, 13, 7, 22, 2, 8, 13, 26, 4, 26, 29, 17, 27, 26, 7, 33, 20, 16, 22, 29, 4, 13, 22, 25, 14, 22, 37, 18, 46, 42, 46, 9, 41, 12, 7, 26, 42, 24, 5, 44, 53, 52, 58, 29, 22, 12, 48, 27, 30, 58, 52, 49, 57, 13, 14, 32, 24, 75, 8, 67, 56, 40, 61, 51, 77, 35, 57, 74, 63, 75, 12, 72, 89, 11, 32, 32, 59, 61, 62, 89, 22, 31, 67, 33, 101, 101, 34, 74, 90, 89, 61, 73, 18, 26, 72, 96, 25, 53, 93, 42, 11, 80, 42, 94, 32, 80, 12, 7, 97, 22, 82, 119, 94, 88, 60, 123, 88, 119, 76, 128, 34, 116, 57, 140, 103, 133, 107, 44, 100, 53, 20, 51, 12, 74, 59, 146, 111, 13, 119, 39, 9, 142, 31, 154, 99, 26, 5, 99, 110, 135, 155, 99, 86, 2, 8, 49, 16, 126, 149, 76, 123, 101, 168, 128, 94, 51, 38, 107, 119, 70, 64, 149, 4, 62, 94, 99, 61, 2, 39, 164, 149, 73, 109, 83, 81, 169, 26, 181, 166, 109, 140, 89, 64, 62, 94, 30, 168, 27, 31, 192, 82, 215, 7, 184, 199, 158, 198, 215, 62, 157, 58, 18, 51, 200, 57, 226, 2, 236, 50, 106, 188, 22, 128, 149, 162, 206, 228, 150, 26, 205, 18, 9, 107, 68, 188, 165, 184, 238, 48, 95, 92, 62, 143, 164, 238, 156, 64, 86, 134, 130, 245, 258, 252, 62, 191, 138, 71, 243, 102, 111, 187, 25, 95, 59, 186, 185, 274, 111, 261, 72, 272, 42, 137, 235, 62, 86, 144, 193, 77, 146, 265, 156, 54, 188, 40, 49, 125, 110, 16, 29, 218, 219, 68, 138, 268, 70, 223, 296, 142, 146, 247, 49, 133, 310, 131, 63, 60, 94, 315, 59, 240, 177, 14, 226, 332, 164, 94, 53, 227, 33, 130, 331, 97, 23, 316, 114, 271, 67, 339, 330, 247, 299, 189, 278, 158, 283, 54, 215, 49, 219, 157, 31, 344, 128, 37, 213, 335, 57, 298, 102, 9, 356, 99, 362, 342, 133, 14, 121, 30, 64, 314, 102, 318, 209, 41, 34, 57, 247, 77, 219, 96, 248, 177, 238, 169, 268, 342, 347, 256, 31, 278, 118, 369, 33, 395, 229, 16, 218, 158, 208, 250, 9, 335, 75, 93, 146, 399, 230, 116, 357, 372, 282, 257, 193, 152, 269, 131, 233, 258, 7, 376, 170, 222, 244, 242, 393, 407, 154, 47, 286, 191, 422, 340, 217, 83, 209, 233, 374, 355, 144, 87, 266, 238, 44, 363, 197, 240, 377, 297, 167, 453, 282, 279, 387, 358, 254, 107, 414, 427, 117, 220, 342, 333, 177, 199, 396, 280, 113, 22, 348, 14, 424, 162, 86, 339, 219, 141, 408, 432, 117, 108, 400, 436, 236, 195, 145, 456, 295, 371, 122, 69, 360, 312, 197, 108, 326, 396, 259, 161, 197, 20, 385, 369, 225, 161, 8, 182, 358, 215, 224, 167, 124, 42, 225, 263, 96, 100, 26, 129, 330, 524, 214, 247, 187, 31, 380, 334, 183, 251, 254, 366, 336, 56, 482, 491, 206, 278, 39, 162, 107, 14, 441, 13, 189, 330, 297, 238, 104, 298, 552, 491, 456, 480, 310, 396, 73, 205, 59, 177, 208, 75, 447, 520, 394, 402, 332, 507, 157, 268, 196, 388, 249, 179, 498, 493, 471, 577, 501, 85, 316, 580, 508, 502, 458, 488, 241, 316, 363, 395, 259, 589, 113, 255, 256, 364, 240, 288, 27, 304, 172, 182, 73, 319, 126, 152, 172, 379, 170, 420, 110, 151, 156, 199, 217, 258, 560, 383, 132, 379, 290, 537, 76, 360, 281, 329, 389, 568, 425, 440, 487, 553, 466, 531, 318, 619, 541, 23, 25, 246, 27, 205, 157, 226, 212, 445, 193, 420, 338, 249, 457, 250, 439, 594, 12, 285, 256, 298, 68, 265, 290, 287, 391, 47, 443, 524, 650, 193, 104, 202, 344, 234, 449, 639, 385, 98, 519, 237, 591, 228, 305, 457, 441, 518, 631, 73, 112, 346, 74, 298, 500, 539, 673, 588, 670, 248, 316, 262, 513, 705, 405, 140, 229, 260, 339, 639, 477, 637, 706, 125, 218, 609, 196, 600, 89, 285, 377, 472, 508, 697, 485, 24, 142, 535, 421, 76, 176, 320, 358, 597, 641, 643, 590, 320, 407, 554, 518, 250, 194, 459, 434, 110, 660, 203, 475, 530, 719, 313, 686, 275, 411, 735, 727, 285, 146, 572, 627, 160, 369, 82, 398, 320, 169, 421, 508, 187, 123, 356, 384, 747, 64, 449, 101, 26, 118, 228, 410, 684, 540, 179, 299, 726, 16, 385, 44, 737, 97, 391, 344, 88, 740, 197, 436, 713, 114, 433, 308, 38, 140, 377, 785, 223, 65, 422, 505, 192, 333, 771, 645, 169, 263, 679, 245, 389, 396, 823, 64, 458, 671, 117, 57, 795, 16, 477, 422, 96, 75, 343, 501, 418, 359, 230, 552, 274, 590, 77, 392, 773, 650, 464, 419, 783, 159, 20, 584, 223, 424, 843, 111, 708, 590, 127, 483, 793, 164, 628, 510, 479, 408, 633, 159, 635, 708, 173, 553, 125, 162, 76, 841, 369, 716, 324, 529, 638, 852, 445, 669, 31, 481, 243, 814, 752, 90, 632, 813, 209, 546, 662, 196, 810, 894, 761, 700, 219, 629, 892, 535, 779, 714, 706, 806, 272, 578, 157, 233, 866, 297, 786, 123, 576, 793, 312, 396, 57, 264, 223, 829, 639, 219, 508, 853, 527, 560, 116, 501, 866, 200, 933, 292, 573, 867, 575, 885, 454, 607, 199, 329, 69, 428, 199, 229, 892, 257, 611, 770, 636, 787, 213, 635, 420, 790, 479, 134, 164, 386, 145, 475, 33, 882, 585, 107, 428, 867, 766, 669, 540, 967, 559, 855, 526, 696, 973, 592, 184, 635, 321, 262, 237, 474, 60, 715, 183, 35, 678, 261, 941, 244, 131, 192, 656, 335, 609, 154, 669, 947, 635, 952, 589, 79, 825, 891, 569, 63, 685, 918, 850, 64, 377, 58, 526, 75, 268, 754, 535, 925, 696, 116, 879, 999, 708, 1019, 880, 984, 71, 923, 810, 394, 127, 450, 198, 409, 835, 348, 143, 524, 194, 178, 54, 545, 274, 840, 608, 604, 14, 819, 417, 787, 509, 965, 322, 1013, 661, 310, 867, 983, 900, 194, 815, 238, 1061, 262, 1063, 714, 316, 613, 559, 725, 239, 899, 447, 87, 151, 862, 902, 327, 110, 612, 118, 212, 123, 626, 407, 816, 832, 994, 705, 59, 943, 529, 193, 437, 1068, 660, 410, 982, 377, 838, 728, 1017, 738, 375, 1023, 489, 81, 758, 433, 774, 938, 936, 734, 281, 1036, 567, 1010, 477, 194, 830, 309, 939, 902, 984, 1059, 619, 212, 591, 480, 818, 483, 951, 811, 129, 212, 170, 307, 1020, 781, 112, 958, 62, 125, 402, 181, 676, 726, 1149, 718, 222, 1091, 506, 329, 988, 634, 843, 639, 436, 1133, 509, 295, 921, 668, 89, 1023, 376, 96, 829, 471, 966, 1136, 238, 1135, 283, 184, 1124, 870, 997, 1024, 479, 1109, 970, 841, 1009, 62, 387, 264, 875, 668, 118, 789, 320, 46, 765, 891, 692, 819, 614, 295, 1004, 520, 1013, 914, 473, 280, 610, 775, 1148, 982, 680, 478, 1017, 1141, 269, 1093, 686, 550, 1000, 672, 50, 133, 871, 538, 82, 117, 365, 466, 984, 712, 127, 517, 490, 482, 112, 798, 634, 342, 504, 778, 184, 1153, 656, 567, 748, 1157, 451, 546, 1168, 1224, 1252, 104, 836, 566, 321, 185, 322, 184, 282, 2, 681, 263, 836, 956, 389, 63, 1062, 1195, 176, 65, 797, 737, 195, 360, 678, 394, 1202, 843, 932, 747, 906, 11, 786, 586, 41, 1214, 244, 209, 1132, 872, 742, 785, 1209, 961, 481, 183, 1187, 889, 63, 1235, 1112, 680, 364, 359, 1073, 1027, 530, 236, 76, 82, 580, 135, 1057, 776, 424, 835, 960, 994, 860, 574, 341, 1307, 743, 730, 151, 82, 298, 1133, 46, 1239, 1310, 909, 420, 607, 1200, 798, 525, 578, 1316, 1127, 63, 221, 342, 1269, 863, 697, 358, 243, 1079, 911, 688, 545, 1300, 1152, 952, 931, 131, 1253, 544, 764, 1324, 35, 1199, 977, 414, 696, 131, 83, 784, 1171, 35, 175, 927, 759, 590, 1005, 1046, 283, 1013, 1044, 824, 424, 1182, 1247, 514, 469, 148, 374, 976, 1120, 801, 531, 211, 221, 1105, 922, 248, 464, 1353, 176, 587, 886, 361, 257, 31, 71, 852, 685, 358, 426, 1335, 124, 677, 690, 234, 419, 31, 1311, 515, 788, 319, 389, 1414, 103, 669, 1300, 545, 330, 162, 82, 886, 499, 596, 372, 206, 470, 486, 1154, 868, 862, 610, 145, 1192, 1356, 862, 799, 370, 701, 1262, 61, 166, 1253, 746, 1202, 218, 46, 1199, 1387, 915, 1050, 254, 527, 223, 246, 179, 5, 692, 492, 215, 458, 251, 601, 1287, 816, 997, 1077, 613, 713, 1158, 1256, 1100, 963, 873, 1473, 162, 549, 239, 510, 1450, 150, 884, 775, 902, 434, 639, 813, 766, 1343, 1154, 1413, 1065, 963, 252, 532, 354, 418, 34, 489, 944, 1075, 956, 995, 854, 1055, 399, 63, 1453, 1511, 1292, 1369, 512, 1052, 494, 560, 650, 803, 173, 1286, 1491, 1413, 965, 4, 486, 802, 982, 655, 544, 320, 1514, 1522, 1413, 1374, 1354, 1438, 216, 777, 915, 608, 311, 865, 58, 241, 1291, 266, 1500, 303, 730, 1005, 947, 1318, 1007, 730, 69, 573, 1388, 348, 1364, 47, 1096, 1253, 1402, 159, 1050, 1216, 865, 578, 818, 669, 777, 572, 1412, 723, 1565, 356, 200, 82, 1017, 1432, 1458, 962, 975, 1544, 786, 1089, 930, 790, 587, 602, 295, 550, 82, 303, 219, 853, 1472, 279, 145, 56, 1324, 386, 1173, 1205, 1080, 1367, 942, 1543, 158, 947, 651, 1071, 1095, 919, 712, 720, 620, 455, 467, 772, 8, 728, 809, 756, 283, 576, 110, 1489, 1257, 188, 230, 296, 1151, 371, 92, 1569, 250, 267, 1311, 115, 1406, 67, 1410, 380, 951, 1292, 1319, 1478, 1511, 1611, 1140, 134, 1297, 1377, 1186, 150, 754, 1526, 1144, 19, 1237, 174, 1160, 1067, 988, 1508, 1170, 705, 202, 1449, 1161, 50, 133, 128, 1155, 1635, 1111, 1534, 1476, 400, 1213, 88, 1659, 348, 1670, 221, 1472, 1614, 1445, 353, 236, 449, 1630, 186, 38, 372, 483, 507, 1688, 214, 506, 705, 505, 838, 289, 506, 534, 974, 1179, 825, 130, 785, 782, 769, 1070, 1709, 756, 1385, 1473, 1590, 1527, 1686, 1459, 1379, 1734, 291, 1673, 945, 1250, 538, 498, 574, 851, 825, 459, 934, 852, 1143, 312, 1434, 685, 1240, 1093, 1363, 1418, 215, 1517, 375, 34, 217, 398, 549, 1715, 523, 735, 615, 943, 1299, 740, 1336, 1117, 1205, 1060, 142, 1193, 1563, 111, 736, 471, 376, 1691, 560, 164, 537, 676, 1459, 758, 1289, 1733, 1755, 1448, 217, 1729, 1779, 284, 677, 732, 1672, 514, 1231, 895, 1455, 1448, 1530, 1399, 198, 334, 295, 116, 1114, 625, 839, 1103, 1642, 1107, 141, 7, 204, 8, 186, 244, 803, 103, 705, 801, 1075, 1254, 1583, 1371, 1804, 49, 712, 173, 1278, 633, 1353, 711, 1612, 37, 1714, 1462, 297, 101, 394, 938, 1255, 775, 1662, 1672, 288, 1683, 832, 317, 315, 645, 921, 1172, 121, 1153, 1696, 280, 436, 587, 943, 478, 1168, 1088, 93, 1383, 427, 1777, 330, 1080, 1251, 1098, 240, 1591, 368, 1591, 48, 505, 1006, 481, 1556, 1374, 52, 154, 831, 134, 835, 768, 1245, 1367, 636, 356, 1865, 424, 933, 1085, 1503, 1214, 1867, 1450, 267, 542, 1196, 598, 1748, 1559, 1835, 1744, 845, 388, 516, 1163, 1219, 1855, 806, 1713, 556, 1116, 1285, 1355, 1806, 1526, 206, 533, 844, 917, 114, 1523, 68, 32, 690, 1175, 1898, 1332, 1320, 1884, 443, 732, 1137, 621, 1748, 20, 381, 859, 1206, 997, 1135, 1403, 332, 361, 1210, 790, 1199, 1476, 158, 127, 733, 173, 1480, 1108, 1635, 1934, 529, 67, 1179, 1441, 34, 115, 1014, 831, 1190, 729, 1568, 50, 1215, 1889, 745, 1441, 109, 315, 829, 295, 1443, 1230, 114, 1359, 1017, 487, 1416, 1585, 138, 396, 896, 852, 1133, 1444, 251, 520, 1167, 527, 1791, 1613, 601, 211, 871, 947, 1570, 17, 998, 618, 1774, 1271, 33, 76, 784, 775, 1511, 1295, 1995, 433, 576, 1092, 1761, 1322, 882, 924, 1944, 1325, 439, 1907, 787, 597, 1193, 1687, 1477, 41, 1322, 1473, 303, 205, 891, 499, 1853, 1547, 427, 96, 1516, 1297, 495, 348, 945, 1021, 79, 95, 244, 1172, 1241, 1496, 593, 243, 890, 1460, 1650, 1957, 809, 956, 1616, 1723, 825, 687, 1874, 1365, 1846, 367, 1104, 1499, 1800, 119, 675, 735, 1826, 1756, 718, 149, 167, 1594, 578, 652, 1362, 1604, 2043, 1992, 1047, 1542, 636, 1131, 1076, 1471, 73, 1925, 1031, 753, 1590, 1696, 293, 649, 1950, 1760, 549, 821, 1219, 1362, 597, 651, 912, 1317, 1936, 601, 1440, 1075, 1713, 392, 939, 1144, 228, 2072, 542, 1190, 1817, 230, 1643, 972, 2, 1967, 870, 1719, 1954, 1369, 893, 1141, 1338, 2096, 1074, 638, 72, 117, 955, 1392, 22, 199, 546, 920, 163, 128, 1548, 189, 1758, 557, 1095, 1287, 2133, 1869, 970, 1347, 2137, 295, 1424, 865, 345, 822, 1005, 1867, 390, 260, 1194, 1477, 308, 311, 1966, 973, 360, 1076, 1591, 207, 1183, 647, 1244, 1919, 410, 819, 256, 1898, 1074, 1402, 7, 656, 1292, 938, 2060, 130, 1014, 1691, 587, 894, 1681, 4, 732, 1105, 2180, 2024, 769, 1070, 1884, 345, 1988, 1012, 4, 381, 1898, 7, 407, 936, 1676, 1709, 761, 977, 643, 2106, 827, 1799, 798, 757, 2054, 1800, 265, 1287, 1916, 240, 1350, 470, 433, 514, 1261, 2070, 450, 463, 1456, 155, 935, 1066, 1108, 547, 1444, 1907, 427, 735, 1472, 1616, 746, 1416, 148, 270, 1952, 1346, 699, 767, 2105, 2221, 1628, 1249, 1630, 541, 1199, 1842, 1101, 360, 1716, 237, 1560, 2132, 371, 402, 1985, 1924, 193, 1017, 379, 8, 1403, 152, 1131, 1135, 2274, 83, 714, 1426, 555, 1037, 2024, 1180, 849, 1438, 43, 1212, 1890, 1954, 1000, 1298, 2147, 817, 2101, 1737, 515, 1201, 111, 364, 1568, 1654, 655, 1224, 1704, 365, 1684, 1750, 1409, 831, 2147, 486, 1692, 1687, 2216, 952, 1701, 201, 33, 534, 620, 1216, 24, 931, 1399, 1072, 1141, 1115, 1662, 331, 2192, 2115, 744, 1231, 143, 981, 1800, 258, 195, 1818, 180, 794, 2025, 2013, 1388, 1571, 262, 1436, 1986, 1758, 636, 1752, 402, 1073, 483, 2280, 656, 1550, 522, 1465, 2345, 269, 1886, 1909, 998, 1157, 1098, 518, 2017, 606, 1306, 2134, 955, 778, 2124, 710, 1720, 2195, 1763, 287, 41, 1273, 47, 773, 1323, 1555, 909, 1262, 13, 614, 2343, 1908, 1263, 1903, 1224, 972, 543, 689, 1255, 2268, 935, 1808, 885, 952, 2279, 336, 1732, 523, 1067, 1027, 442, 777, 1909, 330, 2225, 1896, 1091, 1744, 767, 1387, 2304, 213, 1552, 2101, 554, 2403, 722, 978, 2442, 444, 1715, 2248, 1658, 1524, 266, 1157, 196, 750, 132, 1825, 921, 1986, 994, 1872, 2413, 799, 2372, 516, 1876, 2096, 1637, 1387, 290, 1301, 73, 810, 211, 2352, 1274, 2171, 864, 1601, 419, 481, 71, 444, 1800, 2359, 1362, 1676, 670, 1738, 471, 793, 142, 2235, 1781, 654, 1457, 2313, 525, 1473, 357, 586, 1915, 491, 1896, 2175, 1459, 2287, 1161, 1436, 1179, 975, 2352, 567, 1714, 156, 474, 1103, 552, 2141, 699, 1698, 546, 522, 1987, 2328, 1473, 2379, 2231, 1720, 1013, 2111, 1085, 1331, 695, 1024, 1987, 2404, 1502, 355, 2139, 1510, 1205, 1802, 574, 1552, 323, 1327, 2461, 776, 1947, 173, 2371, 2434, 1017, 2044, 494, 1888, 2376, 85, 2284, 781, 1797, 578, 2493, 1840, 1809, 2109, 574, 2100, 734, 1920, 2174, 1202, 2414, 845, 213, 1886, 2089, 642, 1565, 534, 889, 1744, 940, 1398, 2354, 880, 695, 537, 2139, 1256, 2207, 974, 17, 60, 1290, 1841, 1443, 282, 1147, 787, 332, 2066, 318, 1154, 586, 194, 1541, 603, 2575, 132, 2055, 2436, 970, 2520, 1434, 2310, 1155, 914, 583, 1221, 2519, 1320, 2609, 104, 70, 661, 2584, 394, 60, 2537, 1305, 100, 1174, 102, 2119, 1597, 1441, 1758, 807, 2215, 931, 567, 671, 1530, 2520, 1332, 573, 2642, 2508, 931, 2394, 349, 2455, 529, 1648, 457, 1895, 2455, 1810, 1494, 987, 2289, 1271, 141, 1448, 2055, 541, 1749, 825, 1436, 656, 1196, 256, 833, 211, 1337, 1954, 356, 2086, 269, 2257, 652, 2598, 2345, 2432, 810, 1885, 2664, 2532, 298, 996, 2101, 1410, 2326, 2365, 1602, 1352, 2545, 1247, 2597, 1168, 1590, 1032, 2259, 1178, 1488, 1284, 1137, 706, 1852, 964, 1801, 1335, 1673, 294, 1597, 308, 1521, 296, 522, 49, 1569, 302, 845, 202, 1082, 2664, 642, 2730, 1349, 1344, 756, 2288, 882, 424, 855, 2547, 446, 2473, 2712, 1773, 727, 189, 62, 50, 1016, 2734, 413, 2748, 1178, 1869, 391, 2317, 1286, 205, 17, 2753, 1162, 2289, 1295, 2730, 2731, 2340, 812, 1958, 1012, 2675, 2683, 2645, 965, 2375, 1284, 177, 1012, 2508, 766, 2608, 675, 158, 274, 434, 1258, 2605, 1551, 130, 1370, 2251, 834, 709, 728, 718, 1230, 239, 1716, 241, 2064, 914, 1323, 476, 1316, 569, 2540, 1153, 559, 1082, 2033, 766, 1930, 1608, 1975, 876, 1741, 1173, 2783, 2238, 1391, 1258, 148, 2107, 407, 2462, 2142, 1765, 297, 2029, 161, 2065, 385, 2233, 1224, 490, 1562, 724, 959, 2142, 772, 2682, 1370, 708, 1220, 770, 1626, 746, 1941, 1114, 1515, 782, 2617, 1250, 2454, 2371, 2068, 1468, 2722, 1562, 236, 2511, 2669, 2313, 768, 1672, 661, 414, 141, 220, 1094, 70, 1040, 783, 1576, 654, 1779, 892, 2716, 2614, 1977, 1138, 2669, 2274, 658, 1668, 62, 2183, 623, 2542, 16, 605, 480, 513, 1299, 925, 2550, 1392, 1759, 640, 2511, 1558, 2751, 1957, 1409, 2336, 635, 2693, 762, 100, 721, 593, 1622, 143, 1303, 987, 1724, 547, 2877, 979, 302, 1215, 1994, 1693, 299, 1866, 201, 2504, 382, 2889, 1238, 764, 1739, 1683, 1758, 763, 2127, 1324, 2832, 624, 1760, 2037, 714, 336, 1523, 234, 169, 453, 1493, 1166, 1377, 2548, 2612, 1747, 2946, 2168, 2862, 2648, 539, 2497, 1432, 2857, 2040, 923, 1767, 1161, 2275, 1529, 61, 1707, 2947, 2474, 1233, 2264, 1400, 1049, 1433, 856, 1871, 638, 129, 1500, 2106, 1744, 405, 1986, 1096, 373, 1000, 1064, 1231, 1347, 2572, 2237, 2231, 1232, 178, 2493, 1148, 511, 2915, 529, 2867, 1305, 2794, 1240, 2822, 2696, 2829, 2319, 499, 621, 1525, 726, 2694, 1255, 2433, 2427, 113, 2384, 636, 2785, 1291, 3011, 485, 736, 2124, 1036, 292, 2580, 3019, 2536, 768, 2917, 1230, 1417, 1984, 758, 2676, 2065, 2994, 2453, 299, 2579, 1071, 530, 2477, 1690, 1759, 2639, 2921, 2460, 889, 532, 1245, 272, 1503, 980, 2653, 2769, 2258, 2404, 880, 556, 1855, 661, 1756, 1478, 2646, 2030, 562, 509, 1083, 326, 2115, 1482, 1972, 2546, 2904, 1610, 602, 2865, 1344, 444, 1086, 1447, 2339, 1790, 1287, 2877, 862, 26, 1557, 660, 2398, 2526, 2929, 2673, 916, 96, 2073, 910, 1801, 1184, 2644, 1728, 889, 109, 1329, 740, 1892, 1571, 324, 2871, 326, 2091, 1386, 722, 1986, 2221, 2154, 1704, 559, 3082, 2251, 468, 1823, 1581, 2606, 2327, 110, 865, 913, 3021, 2629, 2213, 3084, 2704, 3118, 2276, 1377, 673, 2543, 1486, 1989, 2466, 382, 657, 2024, 1472, 1447, 1439, 2912, 2178, 1253, 1214, 2133, 591, 2967, 2558, 76, 2274, 310, 226, 1551, 1028, 151, 2893, 739, 2855, 1528, 725, 1859, 1862, 2570, 2046, 1105, 2374, 1515, 2704, 1812, 1651, 752, 3008, 2648, 614, 1610, 1470, 3010, 1642, 350, 606, 1170, 889, 546, 2826, 966, 319, 2208, 751, 2835, 2270, 350, 3102, 336, 959, 1397, 1190, 34, 2191, 411, 77, 1847, 1250, 3113, 2192, 387, 2777, 1645, 689, 2669, 979, 2751, 2638, 1129, 344, 2475, 2115, 2300, 2759, 2169, 2876, 2490, 2079, 3080, 2110, 813, 3136, 1667, 2005, 1909, 2079, 962, 313, 2727, 1314, 2821, 2640, 375, 2545, 1005, 1739, 2902, 2549, 1544, 358, 2063, 1320, 155, 1445, 41, 286, 2004, 1870, 2496, 2465, 466, 13, 2065, 1759, 2022, 2115, 1049, 3070, 2096, 1514, 2604, 1905, 883, 529, 2159, 1195, 2606, 2143, 1014, 3104, 2285, 2225, 2363, 377, 1579, 407, 2220, 2099, 2995, 2179, 1219, 268, 2851, 3205, 2426, 3134, 1927, 1374, 182, 2424, 543, 334, 1236, 1218, 2732, 3181, 797, 644, 2902, 1676, 3214, 314, 1414, 3295, 2589, 2003, 654, 125, 927, 1281, 3104, 1968, 1297, 854, 1910, 958, 3205, 2987, 910, 1099, 2044, 1548, 752, 37, 2730, 1597, 2437, 2611, 452, 302, 2536, 2289, 3093, 3337, 2061, 1358, 22, 3112, 739, 2838, 1611, 1858, 755, 1001, 3274, 695, 3180, 2522, 1125, 850, 1677, 1253, 3293, 2779, 1557, 1444, 2165, 1980, 921, 270, 1496, 1712, 408, 2070, 1666, 375, 2692, 123, 3218, 679, 2124, 1337, 49, 3273, 1241, 310, 2744, 2525, 661, 1852, 2134, 1793, 997, 3355, 3011, 739, 2371, 2307, 1152, 3324, 2632, 3018, 535, 416, 2495, 1956, 63, 461, 1918, 400, 3078, 3045, 663, 1814, 2077, 2053, 824, 255, 2826, 1542, 3236, 133, 1564, 805, 2925, 2603, 943, 64, 230, 2331, 632, 749, 2387, 2014, 52, 2953, 1456, 2550, 2565, 3252, 1900, 86, 3193, 2830, 1021, 160, 2384, 2867, 50, 1125, 2326, 1496, 699, 3246, 2241, 1906, 117, 2803, 1418, 622, 179, 3139, 722, 1387, 2766, 2611, 422, 1226, 2665, 1560, 335, 493, 2264, 3072, 3208, 17, 1997, 1777, 658, 299, 1098, 1557, 3315, 2660, 1628, 2309, 2427, 3196, 1966, 1745, 3177, 2812, 1776, 3335, 2683, 1943, 2086, 1510, 2109, 2772, 1257, 536, 3093, 2332, 552, 3188, 2995, 2397, 1077, 1908, 2445, 1898, 1091, 50, 2596, 1984, 3270, 149, 2057, 1786, 359, 1025, 1938, 1788, 660, 3376, 2355, 1998, 441, 2816, 2192, 2276, 272, 1213, 1202, 1136, 605, 3327, 3322, 2125, 3475, 3273, 2234, 1046, 266, 1030, 577, 1290, 980, 1001, 2819, 2914, 473, 3393, 2279, 2135, 1514, 693, 590, 1766, 1445, 208, 2974, 2578, 3451, 3031, 2797, 2546, 1145, 1712, 2681, 1665, 1465, 1188, 195, 2766, 402, 270, 2259, 2024, 652, 2511, 2712, 2766, 1879, 1737, 3543, 417, 1518, 243, 271, 2267, 2078, 3575, 2509, 3482, 2558, 1744, 804, 733, 1076, 1748, 1152, 654, 1917, 3311, 1115, 285, 3085, 2865, 1993, 1219, 3464, 2937, 1320, 1411, 116, 128, 1457, 1304, 3417, 3406, 2237, 1932, 667, 193, 2773, 2282, 728, 2288, 2873, 2823, 1519, 1572, 3365, 2778, 1375, 1164, 366, 3313, 1682, 2001, 3530, 271, 3355, 2823, 748, 874, 2642, 2512, 650, 425, 3494, 101, 627, 1772, 1098, 809, 2807, 2231, 83, 918, 2063, 2187, 944, 1139, 3634, 3660, 2325, 2362, 1054, 1029, 2627, 1988, 805, 3672, 2932, 2631, 1065, 1386, 3184, 3319, 2137, 1881, 130, 115, 2726, 2092, 1623, 1889, 3022, 2852, 1720, 1626, 433, 3559, 1669, 2475, 791, 173, 3413, 3539, 1026, 2070, 196, 3208, 1957, 2030, 972, 3165, 3162, 2702, 1712, 2137, 3323, 3491, 2029, 2083, 977, 433, 2638, 2154, 1249, 1302, 3495, 3505, 2234, 2162, 633, 627, 3212, 332, 1635, 360, 380, 3293, 2364, 2856, 3637, 411, 3168, 3488, 2739, 1945, 3311, 196, 2285, 2161, 648, 1590, 2348, 3073, 2983, 1103, 1362, 540, 1307, 2544, 1011, 1300, 3756, 49, 2142, 2060, 1065, 710, 3180, 333, 1415, 1255, 508, 3037, 183, 769, 3586, 256, 3770, 399, 2888, 2130, 3594, 454, 3394, 3290, 1733, 2823, 623, 1463, 2950, 3661, 1982, 2869, 3096, 3576, 3550, 2225, 2434, 2035, 2451, 3795, 2886, 2272, 1011, 969, 3057, 3201, 1956, 1877, 1347, 1950, 2864, 2743, 2510, 2037, 971, 115, 2042, 3063, 1964, 1124, 391, 748, 2690, 3084, 1932, 1789, 1105, 1057, 3140, 2322, 1543, 612, 3388, 1405, 1635, 1974, 2464, 2176, 1137, 3726, 2773, 2785, 1736, 1672, 3623, 1384, 2366, 2625, 2409, 1679, 474, 840, 2641, 2560, 1136, 2281, 336, 199, 1669, 2202, 1762, 1542, 386, 3777, 3226, 3015, 1762, 2110, 192, 522, 3387, 2643, 2482, 2219, 295, 3845, 2276, 2874, 1892, 1441, 1234, 764, 3026, 598, 3014, 3345, 1090, 2088, 3419, 3375, 1420, 1648, 1935, 2587, 3098, 374, 3779, 2570, 2196, 2164, 3532, 793, 2842, 2715, 2274, 2688, 1097, 1312, 266, 3640, 2051, 3376, 1321, 981, 568, 3813, 3100, 3424, 941, 2310, 493, 42, 3918, 3354, 2460, 2178, 750, 1145, 3862, 710, 2646, 1839, 1614, 2081, 526, 895, 2207, 2453, 1629, 1715, 1324, 1018, 2608, 391, 2843, 2785, 1936, 2082, 1239, 2925, 3268, 3195, 2478, 3126, 3031, 984, 887, 3743, 49, 2579, 1304, 2396, 23, 486, 2966, 73, 1701, 2257, 2142, 2199, 891, 1525, 2586, 2910, 2256, 2745, 860, 880, 2521, 3649, 3471, 3135, 3084, 2671, 546, 87, 3544, 2944, 2971, 575, 1254, 497, 411, 1038, 3763, 3959, 1760, 2713, 498, 1205, 1339, 1644, 2578, 12, 2565, 2782, 1885, 1327, 3883, 3883, 80, 8, 3006, 3551, 647, 1441, 785, 847, 783, 3555, 2198, 2160, 2129, 1306, 1503, 791, 2592, 3550, 3199, 3227, 2478, 2271, 1042, 3768, 3473, 3914, 2527, 37, 1166, 2612, 787, 958, 1434, 1595, 2681, 2743, 2720, 1875, 691, 2034, 3763, 620, 186, 3762, 3400, 2421, 1356, 1926, 208, 907, 3186, 797, 2295, 3121, 2616, 2045, 1013, 2442, 72, 3794, 3316, 3594, 3046, 93, 597, 1409, 691, 1350, 1015, 419, 3286, 3372, 1284, 2695, 1241, 2618, 63, 4059, 694, 890, 3176, 3960, 2007, 1574, 1131, 2361, 1053, 455, 2968, 260, 2705, 3252, 1734, 2375, 658, 1138, 1143, 763, 3584, 68, 2511, 2870, 2289, 3144, 821, 1334, 3415, 620, 3650, 3180, 3332, 3775, 1691, 2199, 1886, 787, 3845, 839, 3900, 3276, 2458, 2303, 2409, 3539, 3682, 1952, 4098, 870, 728, 79, 2596, 2670, 1842, 1664, 939, 2654, 20, 1246, 1087, 1154, 811, 11, 2771, 1423, 1841, 1948, 2463, 1463, 3199, 647, 4074, 4020, 3674, 292, 2572, 3634, 3097, 2811, 422, 2618, 3713, 3582, 76, 3203, 3993, 3272, 1769, 3043, 1527, 1571, 947, 1793, 2909, 1163, 4184, 431, 3312, 4128, 2322, 2243, 1069, 1782, 1175, 3326, 2361, 939, 3918, 1193, 3507, 3662, 1494, 2574, 1085, 2075, 1818, 2938, 1054, 1155, 970, 1067, 3656, 892, 2098, 2244, 2874, 1917, 2738, 3069, 713, 1514, 473, 221, 723, 294, 2253, 3056, 2751, 2958, 2440, 3053, 1460, 1145, 384, 1357, 1645, 383, 3860, 3743, 2912, 3216, 2235, 3720, 973, 3041, 1816, 2418, 1744, 2229, 581, 3733, 4135, 999, 3392, 1921, 1724, 3551, 3161, 3118, 3401, 2998, 1247, 2306, 890, 1374, 398, 2199, 3007, 119, 3842, 4228, 2784, 3435, 2949, 2875, 2117, 2254, 1693, 1870, 3784, 445, 438, 4266, 229, 1513, 3454, 83, 3448, 3470, 1784, 3899, 2620, 2477, 1759, 2552, 3017, 1698, 130, 982, 54, 197, 413, 968, 3227, 339, 3834, 206, 2824, 3149, 1923, 1848, 1411, 2344, 1446, 3215, 430, 992, 1051, 920, 354, 1519, 3404, 769, 4051, 3301, 2578, 62, 2792, 3354, 1989, 3405, 1569, 2228, 2170, 2149, 1306, 884, 889, 2392, 3738, 1147, 791, 3867, 4046, 49, 3032, 3806, 3368, 4290, 2067, 94, 1623, 2950, 1658, 1835, 2689, 1938, 629, 1445, 896, 255, 624, 1508, 51, 1278, 900, 254, 4071, 862, 3624, 2468, 3137, 3690, 3487, 4292, 941, 2471, 3659, 2508, 2303, 2513, 1561, 1562, 871, 1010, 554, 1022, 3432, 4382, 1188, 1806, 3953, 1954, 4104, 19, 2724, 3839, 3749, 93, 1861, 3775, 3650, 3640, 2611, 2906, 605, 2845, 1897, 2804, 2184, 3946, 2436, 2058, 968, 1543, 1332, 1663, 4048, 1024, 26, 117, 471, 1273, 3795, 696, 4172, 4320, 3314, 449, 3275, 3591, 3277, 3134, 3676, 1364, 1718, 3057, 2725, 3246, 3816, 3371, 1569, 2426, 2118, 2721, 1673, 3621, 1457, 2444, 2399, 2364, 2496, 2741, 1465, 1487, 436, 1465, 2383, 2215, 3778, 785, 597, 698, 327, 1233, 4260, 4270, 202, 457, 577, 1181, 3505, 364, 63, 245, 225, 191, 3156, 434, 3760, 4299, 3674, 4011, 2606, 3711, 3319, 3609, 3283, 4462, 3687, 3806, 2693, 3064, 2826, 154, 2010, 3110, 3191, 3758, 3632, 4292, 2444, 3138, 2140, 3348, 1858, 3831, 2438, 2367, 3168, 2933, 2749, 4019, 2292, 2895, 2131, 2752, 2217, 2656, 1606, 2645, 2175, 3015, 1520, 3204, 1970, 1744, 1776, 2650, 1921, 4503, 1880, 1937, 1760, 2785, 1803, 1355, 416, 1920, 1294, 1548, 1557, 2569, 973, 3083, 2432, 3112, 1502, 2971, 1050, 1319, 2197, 856, 2557, 4053, 4525, 3183, 1908, 2915, 2638, 2203, 1162, 2446, 1924, 3945, 1338, 3064, 2041, 2874, 2712, 2581, 2244, 3442, 2539, 2589, 2279, 2669, 2146, 3609, 1626, 3350, 2469, 2625, 2143, 3895, 2448, 3163, 2011, 2997, 2849, 4487, 2330, 2728, 3142, 2977, 3665, 4256, 2465, 3838, 2914, 4461, 3435, 4116, 1792, 197, 3590, 4549, 4243, 567, 3787, 3932, 3184, 4386, 180, 1526, 1786, 1090, 245, 818, 1178, 884, 3144, 728, 4091, 677, 4581, 1832, 359, 1863, 1044, 1581, 1405, 2629, 1031, 1418, 1987, 1135, 1561, 2771, 916, 2319, 1353, 2438, 1563, 3414, 1259, 2831, 1804, 3032, 2719, 333, 2761, 2519, 3868, 3436, 144, 4223, 1034, 4124, 3340, 4388, 44, 1137, 3503, 1091, 4075, 646, 207, 1172, 93, 488, 99, 2003, 1354, 1876, 4393, 1069, 1595, 1961, 2159, 3238, 1300, 2984, 2159, 2737, 2766, 4624, 1394, 3286, 3895, 4528, 3371, 886, 3215, 3412, 3977, 335, 4501, 1205, 2767, 1331, 664, 1263, 2035, 2250, 656, 1625, 1048, 2255, 1689, 3440, 1434, 3102, 3103, 3131, 3195, 4114, 1790, 2874, 3032, 4176, 3533, 4706, 3559, 338, 387, 403, 282, 1874, 456, 991, 453, 1553, 1375, 4400, 382, 2266, 2398, 3045, 3296, 3311, 2194, 3652, 3150, 3991, 3659, 940, 2998, 1226, 143, 321, 49, 1594, 1129, 674, 1748, 1702, 2164, 2510, 97, 4079, 2516, 2562, 3878, 3376, 2672, 2967, 4528, 209, 4473, 1654, 3762, 51, 729, 1405, 282, 1068, 413, 1116, 2218, 2058, 2042, 2572, 2483, 4022, 3495, 3892, 4663, 1383, 3523, 4332, 4246, 542, 483, 2985, 4166, 1199, 2875, 2643, 2786, 3481, 2313, 3942, 1062, 3066, 2597, 333, 3029, 57, 510, 2078, 810, 1818, 795, 1142, 353, 2183, 2621, 3463, 4672, 2725, 2648, 3722, 3915, 199, 3633, 133, 458, 566, 900, 3013, 920, 1087, 1085, 2555, 2990, 3416, 1570, 3751, 2494, 4312, 4607, 1977, 3911, 1809, 200, 640, 1231, 2794, 1527, 1123, 1988, 2961, 3272, 4836, 1421, 33, 3710, 1205, 1258, 639, 4147, 1734, 1347, 2620, 2497, 4449, 2519, 4180, 2921, 4713, 4871, 1190, 1420, 462, 822, 1474, 1569, 2781, 1012, 2658, 2043, 2832, 4511, 4871, 3378, 3941, 31, 416, 501, 2912, 769, 1045, 2162, 3704, 3558, 3095, 2971, 4284, 3292, 4843, 4483, 1922, 4381, 2068, 2575, 3265, 2536, 3763, 2632, 3185, 4375, 770, 4562, 2405, 3129, 1049, 1227, 2996, 2771, 3151, 2729, 3951, 3702, 4562, 4364, 1468, 4423, 1111, 1833, 2433, 2404, 4365, 2785, 3569, 3431, 4820, 4766, 632, 3885, 2675, 1009, 2010, 2261, 4033, 2816, 3165, 3747, 3587, 3737, 2101, 4452, 1477, 1858, 3158, 2898, 3270, 1863, 3820, 3496, 3489, 986, 1809, 308, 1158, 1893, 3378, 2392, 3700, 2532, 2865, 4966, 4357, 4816, 2384, 260, 1850, 1288, 2891, 4642, 2998, 3258, 3804, 4212, 529, 4696, 3575, 1443, 1939, 4077, 3739, 3503, 1233, 4964, 3977, 68 }; int main(){ int T; scanf("%d",&T); while(T--){ int n;scanf("%d",&n); printf("%d\n",val[n]); } return 0; }