#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define int long long int
const int N = 2e3 + 100;
const int md = 1e9 + 7;
const int INF = 1e9;
int32_t main(int32_t argc, char *argv[]) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> a = {-1, 0, 3, 2, 15, 4, 5, 8, 12, 11, 9, 10, 23, 27, 17, 19, 20, 18, 33, 21, 39, 35, 51, 34, 36, 44, 80, 38, 45, 37, 104, 72, 42, 88, 92, 87, 135, 70, 107, 69, 132, 75, 83, 73, 77, 84, 189, 82, 74, 133, 183, 142, 380, 85, 156, 139, 204, 137, 168, 157, 141, 155, 147, 179, 138, 164, 180, 148, 153, 146, 443, 178, 150, 154, 171, 273, 269, 173, 165, 149, 266, 285, 275, 283, 371, 324, 296, 170, 624, 276, 290, 274, 281, 313, 540, 292, 278, 307, 314, 282, 591, 349, 308, 300, 332, 277, 347, 294, 648, 306, 299, 532, 744, 339, 293, 301, 537, 297, 546, 309, 534, 340, 696, 580, 561, 538, 338, 330, 558, 298, 708, 533, 627, 611, 570, 664, 804, 556, 564, 604, 663, 550, 341, 668, 651, 566, 555, 562, 1274, 581, 549, 605, 588, 557, 1400, 553, 669, 653, 603, 587, 1070, 565, 1145, 659, 723, 619, 585, 595, 852, 691, 621, 554, 1199, 676, 717, 724, 660, 601, 1112, 596, 1139, 658, 1067, 722, 684, 586, 594, 1111, 1688, 602, 690, 598, 666, 1065, 618, 1093, 1499, 683, 1220, 1240, 1100, 1117, 1124, 1077, 1175, 685, 693, 661, 1163, 1099, 597, 1239, 1319, 1066, 2151, 1161, 1307, 1141, 1097, 1383, 1259, 1107, 2085, 1131, 1187, 1101, 2607, 1165, 1181, 1192, 1133, 682, 1379, 1243, 1643, 1113, 1298, 1108, 1421, 1129, 1442, 1125, 2232, 1098, 1253, 1684, 1106, 1372, 1316, 1210, 2316, 1114, 1235, 1110, 1331, 1188, 1172, 1306, 3171, 1258, 2328, 1177, 1130, 1170, 1388, 1452, 1229, 1332, 1373, 1236, 1397, 1426, 1196, 1707, 2235, 1174, 2268, 2284, 1109, 1242, 1178, 1234, 1202, 2150, 1451, 1330, 1190, 1323, 1355, 2626, 1226, 1195, 2844, 1389, 2736, 1453, 2211, 1317, 3180, 1363, 1325, 1173, 2829, 1197, 2871, 1189, 1205, 2285, 2343, 1357, 1193, 1333, 2331, 2138, 3432, 1237, 2754, 2225, 2802, 2252, 1364, 2210, 2508, 2281, 2376, 2407, 3240, 2344, 3483, 2501, 2154, 2234, 2277, 1362, 2805, 1354, 1322, 2212, 3219, 2467, 2259, 1194, 2664, 2201, 2403, 2194, 2133, 2420, 4316, 2228, 2964, 2249, 2850, 2282, 2265, 2908, 2361, 2612, 2253, 2326, 2220, 2198, 2445, 2260, 2490, 2230, 2700, 2647, 2202, 2522, 2355, 2330, 2391, 2795, 2226, 1365, 2514, 2266, 2214, 2258, 2610, 2374, 4637, 4251, 4589, 2219, 2262, 2404, 2484, 2356, 2250, 2348, 2325, 2653, 3435, 2197, 2397, 4315, 2892, 2668, 2373, 2221, 2421, 2213, 2907, 2342, 2229, 2476, 2358, 2728, 2217, 2651, 4679, 2450, 3243, 2354, 2613, 2347, 5960, 4260, 2517, 4299, 5075, 2411, 2379, 2261, 4931, 4242, 2859, 2707, 2406, 2341, 2763, 4839, 2643, 2413, 2349, 4420, 4556, 2698, 4925, 2387, 5807, 2345, 2637, 4467, 2739, 2861, 4268, 4807, 4301, 2218, 6551, 2357, 2409, 2381, 2724, 4308, 4796, 4563, 2469, 2405, 4634, 2708, 2772, 2393, 2661, 2740, 4409, 4374, 4262, 2453, 2388, 4569, 4850, 4314, 2706, 4306, 4529, 4267, 2634, 4923, 4874, 2642, 4553, 2732, 4310, 5848, 2346, 4245, 4298, 2386, 4439, 2378, 5924, 4741, 2394, 2410, 4712, 4269, 4499, 2738, 4466, 2390, 8475, 2666, 4277, 4696, 8421, 4824, 4265, 2474, 4373, 4396, 9189, 4660, 8403, 5389, 4490, 2731, 4460, 4828, 4724, 9007, 4445, 5077, 4700, 4791, 4421, 5271, 8739, 4390, 5528, 4695, 4469, 4309, 4406, 4554, 4748, 4500, 2733, 4662, 4433, 2741, 2709, 2645, 4505, 4395, 4658, 4443, 4706, 4921, 5042, 2389, 5405, 4498, 10044, 4645, 5516, 5395, 4427, 4266, 8358, 4530, 4829, 4389, 6824, 4722, 6548, 4653, 4454, 4701, 4397, 4684, 4838, 4915, 4649, 4461, 4502, 5197, 4922, 4393, 9597, 4435, 8484, 4425, 5357, 4981, 4523, 5800, 5018, 4771, 5444, 5229, 5288, 4405, 5045, 4699, 4841, 4683, 4661, 4429, 4457, 4776, 4916, 4725, 5339, 4749, 2730, 4533, 4940, 4453, 5723, 5581, 5267, 4441, 4805, 4837, 5843, 5394, 4517, 5221, 9099, 4971, 4436, 4681, 4715, 4521, 8595, 5464, 4691, 4755, 5531, 4501, 8526, 4650, 8817, 5586, 5555, 4939, 4394, 4770, 8622, 9254, 4685, 4717, 5210, 5323, 8556, 4434, 5468, 4426, 4907, 4842, 8808, 5331, 4442, 5796, 4787, 4458, 8628, 4947, 8949, 5268, 5540, 4438, 5474, 5427, 4697, 4825, 5780, 4713, 4772, 8756, 5354, 4692, 4901, 8491, 4709, 8650, 8940, 4756, 5300, 4813, 8742, 4941, 8601, 5476, 4820, 4522, 8796, 5325, 8856, 4761, 9303, 4953, 4682, 8594, 5804, 5332, 4754, 4690, 9261, 4917, 8814, 5292, 5420, 4948, 8493, 8626, 8550, 5493, 4826, 4698, 9495, 4780, 5522, 5554, 6827, 4818, 4694, 9098, 8802, 5452, 8661, 5274, 8598, 8521, 10098, 9142, 5330, 4437, 4970, 8860, 9009, 4714, 4946, 8501, 8985, 4786, 8619, 4954, 9108, 4762, 9831, 4810, 9309, 5803, 5426, 8797, 5483, 5547, 8745, 4774, 5291, 9356, 8871, 5451, 9399, 8996, 8841, 8549, 8934, 4906, 11079, 4779, 8910, 8629, 10506, 8621, 8982, 5485, 9060, 9011, 9291, 5557, 8532, 5805, 9444, 5269, 5549, 8867, 9258, 8795, 8757, 5293, 5459, 5421, 9624, 8617, 5285, 4693, 8490, 5301, 8937, 8597, 4781, 8872, 8913, 8861, 4757, 4789, 9114, 4773, 9915, 4821, 9594, 8530, 9333, 8522, 9963, 10010, 5453, 9676, 9501, 4777, 5429, 9383, 5333, 8777, 8889, 8554, 8811, 10091, 8859, 10075, 8787, 8534, 4949, 8746, 11187, 8806, 9669, 8851, 11592, 9451, 9051, 9125, 9507, 9766, 9798, 5460, 9867, 9379, 8781, 10093, 10536, 8813, 8907, 9683, 12891, 8842, 9357, 8998, 9453, 8915, 9675, 9062, 9414, 11624, 11859, 8890, 9384, 10388, 9069, 9926, 10404, 8618, 9771, 9512, 8883, 9109, 9540, 9689, 16790, 5458, 8793, 9842, 9300, 8878, 5450, 5418, 9435, 5290, 9657, 8788, 9891, 8921, 8868, 8905, 8805, 9043, 9765, 9401, 16994, 9317, 4778, 10420, 9804, 8852, 9033, 9571, 9957, 9065, 9354, 8909, 9588, 9506, 8997, 8533, 9885, 8884, 8778, 11468, 9378, 8857, 10653, 9869, 10980, 8786, 19988, 9497, 17201, 9037, 8850, 9445, 10029, 9130, 9690, 11042, 9306, 9001, 9819, 10708, 10452, 8794, 9627, 9049, 9402, 9803, 16805, 9419, 10068, 9529, 8790, 8876, 9651, 9682, 18824, 10844, 9939, 9875, 8886, 8914, 11106, 9619, 11154, 9508, 9564, 9380, 11346, 9364, 10839, 10583, 11571, 8810, 17174, 10090, 12948, 8918, 10458, 9835, 17252, 9322, 17501, 9866, 16730, 8882, 21296, 10610, 9369, 8858, 9450, 9830, 9636, 5461, 9417, 8906, 9066, 9652, 9396, 9433, 9042, 9530, 17105, 8870, 20717, 9674, 11628, 9050, 9837, 9034, 10596, 9542, 18767, 9421, 10548, 9892, 9933, 9805, 17483, 8875, 18326, 9572, 10389, 9046, 12972, 9428, 17003, 10919, 10866, 11564, 13659, 9388, 11469, 9002, 9876, 17893, 17333, 9301, 10413, 9524, 9366, 19927, 10797, 9398, 19508, 8789, 9516, 9565, 10644, 9625, 13611, 9817, 16973, 11060, 10860, 9493, 10572, 9589, 11436, 9370, 8877, 9541, 10971, 9434, 8853, 9685, 11052, 8885, 9618, 8869, 9426, 9650, 18008, 9548, 11691, 8917, 17321, 17206, 9900, 10642, 19076, 10546, 10587, 9382, 9510, 8873, 10539, 10909, 10956, 9430, 10674, 17227, 10893, 17815, 19589, 12971, 10869, 9563, 11595, 9802, 17510, 10453, 9387, 9418, 9810, 10571, 19223, 11117, 9522, 9638, 16997, 9622, 9906, 17113, 9579, 9515, 17831, 18252, 18653, 19779, 18533, 9643, 10533, 9547, 9045, 17044, 9882, 18007, 19412, 17235, 17645, 11435, 18038, 9574, 10605, 10541, 9894, 9365, 17576, 10667, 17225, 17076, 18059, 10955, 17108, 9581, 11091, 9389, 9834, 10579, 10914, 10963, 18278, 9509, 9381, 17704, 17042, 9653, 18707, 9397, 10890, 21699, 10794, 17974, 9645, 9517, 9555, 17881, 17513, 10861, 18251, 10829, 17963, 9385, 17555, 17617, 16982, 11437, 10677, 10549, 17849, 17322, 17684, 9637, 9513, 10573, 22034, 11053, 11085, 17641, 23003, 17989, 8874, 9941, 19532, 9577, 18020, 17490, 9429, 9901, 21416, 10597, 18083, 17002, 9549, 10916, 17570, 17046, 9525, 19132, 19607, 9893, 18281, 9877, 9573, 17110, 9621, 17869, 11604, 10957, 19643, 18124, 17498, 10900, 11061, 11092, 10836, 10964, 9561, 10580, 18791, 17494, 20651, 17752, 10932, 18277, 33588, 17098, 17594, 19612, 17882, 17805, 19379, 17611, 9813, 17062, 21095, 9556, 17819, 18580, 18635, 18756, 17258, 17721, 18596, 17826, 17234, 10898, 20171, 17619, 18011, 19078, 17843, 19341, 18827, 10826, 18221, 11602, 18803, 10538, 20891, 17700, 21620, 10834, 17756, 11090, 21320, 19047, 10578, 17514, 35298, 10924, 10962, 10570, 18899, 17238, 18722, 17710, 11082, 9386, 18131, 10586, 17561, 20883, 10602, 17194, 20915, 9554, 17642, 17751, 18713, 17554, 17609, 9514, 9546, 19189, 17588, 9578, 21107, 9562, 21704, 19077, 9642, 17778, 17690, 19780, 17069, 18106, 20021, 17722, 17045, 18058, 18905, 10930, 17993, 17077, 19619, 17061, 9558, 10954, 21188, 10858, 27479, 10666, 18776, 18637, 18137, 17109, 19160, 18604, 18845, 18582, 20900, 17620, 23852, 18121, 19043, 17065, 20051, 9898, 18266, 17493, 18029, 19032, 18644, 18889, 21212, 18724, 18614, 18250, 17558, 19930, 19172, 17772, 21773, 17590, 21947, 18586, 18125, 17716, 10923, 17812, 21461, 18262, 18893, 18132, 17846, 20148, 17708, 18780, 23132, 17757, 19730, 18874, 19853, 17562, 20309, 17817, 33933, 17685, 18068, 18610, 23180, 17626, 19874, 17781, 25943, 18714, 19292, 17586, 22733, 19641, 17618, 19036, 35736, 18598, 18650, 18025, 36378, 18009, 21035, 17877, 17237, 18073, 18746, 17740, 33498, 17574, 18218, 19159, 21266, 18138, 19031, 18021, 33462, 10925, 19769, 17622, 17702, 18066, 35595, 17745, 21770, 10933, 10965, 10837, 20069, 18130, 10581, 18646, 23138, 19804, 17579, 20052, 21227, 17610, 21029, 17755, 20843, 36317, 18092, 23389, 21335, 18634, 36105, 19179, 34662, 18102, 34152, 9557, 17714, 18852, 18788, 18826, 19538, 19042, 18581, 17830, 33969, 17707, 17771, 19642, 21284, 17994, 21779, 18709, 19850, 19308, 21092, 19270, 17066, 17739, 21671, 17835, 19763, 17818, 19181, 17557, 21068, 20845, 18605, 18070, 18122, 19258, 20042, 17766, 18098, 18597, 19013, 20050, 23372, 17581, 18890, 18010, 20819, 19174, 33882, 19620, 19058, 18261, 17573, 17773, 21611, 22315, 18074, 19044, 21419, 17589, 22892, 17701, 18836, 19812, 19037, 18601, 19373, 18726, 18989, 19860, 18086, 19020, 21365, 17845, 34665, 20139, 20789, 17577, 21155, 18742, 17747, 18841, 17837, 33971, 34533, 19609, 18860, 18985, 19052, 17737, 35301, 22932, 19925, 18091, 22220, 19269, 39384, 19252, 19562, 21045, 21800, 19107, 17705, 21828, 19163, 18738, 21875, 17829, 18779, 19177, 19661, 22701, 17621, 19756, 19829, 19858, 19244, 22173, 20837, 17769, 20909, 22317, 34395, 17833, 18866, 18645, 36450, 19668, 19781, 23892, 17741, 19291, 19112, 19035, 17717, 36238, 19307, 21723, 33945, 18795, 19019, 18763, 19148, 20901, 17765, 10922, 19085, 21972, 19628, 18133, 17813, 20820, 23195, 20133, 21917, 18093, 23339, 21339, 34995, 19173, 20117, 19141, 17753, 21147, 18725, 18790, 19349, 19302, 21794, 26283, 37620, 18085, 34074, 18069, 21269, 19129, 18854, 21075, 19238, 19309, 23243, 19275, 35643, 18733, 18797, 19674, 40029, 17748, 19883, 19099, 18842, 20778, 36549, 23202, 18089, 18859, 19610, 19666, 35211, 21666, 21848, 19819, 19250, 34004, 22178, 18771, 19634, 19051, 19091, 18729, 18005, 34387, 18761, 21069, 38370, 20818, 18602, 19755, 21203, 36155, 19787, 19027, 33942, 19147, 22955, 21939, 19046, 23149, 35688, 17578, 19622, 20053, 19106, 20826, 23219, 19155, 19283, 34478, 34413, 19893, 37497, 20842, 33621, 21907, 18986, 26964, 19082, 18741, 34650, 22867, 19658, 19885, 18869, 17746, 21683, 18793, 19130, 18765, 37833, 17706, 35700, 35188, 17738, 21331, 37257, 21715, 37698, 17770, 36393, 17754, 35379, 33970, 23204, 36259, 35121, 19123, 34002, 23380, 17834, 22125, 19877, 18789, 35913, 19237, 19301, 18853, 37800, 21156, 34452, 21847, 43275, 35432, 19757, 21076, 17750, 18777, 36264, 19161, 19277, 21811, 23252, 21093, 37035, 22861, 18857, 21874, 37992, 34006, 35028, 34393, 21140, 21898, 21962, 19108, 21293, 21349, 21197, 21418, 41700, 19605, 20906, 18772, 19289, 34102, 33963, 18837, 19049, 34405, 36405, 19629, 36531, 21172, 21650, 19861, 35766, 19149, 20138, 34450, 36459, 19092, 19028, 19621, 35118, 37171, 35277, 19045, 19637, 19156, 23186, 34514, 19253, 19813, 21860, 19284, 34098, 19765, 19124, 18090, 40134, 21138, 21074, 35380, 37818, 36425, 34476, 34091, 38994, 22162, 22226, 34198, 19097, 21301, 36564, 21868, 21908, 19801, 22100, 18730, 34518, 23122, 21716, 23212, 21332, 40013, 39195, 35026, 37218, 34219, 21812, 19090, 21932, 21082, 18770, 35737, 37704, 19669, 38754, 19018, 21164, 18762, 36114, 21804, 40155, 35633, 19796, 35602, 36237, 34987, 33957, 19026, 46125, 18778, 52584, 19306, 37794, 21877, 18794, 21973, 34506, 21589, 36258, 35609, 34482, 35246, 35142, 19116, 38829, 19282, 19154, 21906, 41628, 35924, 21938, 27307, 35730, 35479, 36693, 18774, 41820, 19290, 19034, 22866, 37164, 36394, 34458, 35945, 19274, 21354, 21098, 22194, 38130, 38200, 34131, 40133, 37602, 35978, 35172, 21330, 34221, 19030, 21170, 21714, 34470, 21682, 38088, 38533, 35406, 17749, 36498, 19882, 19094, 35093, 36069, 35252, 34410, 21322, 21194, 18858, 34089, 19794, 38628, 35180, 37986, 41906, 34005, 35467, 42732, 19122, 21851, 19818, 36453, 19786, 36132, 34981, 38211, 19050, 19802, 19146, 47709, 35165, 19754, 19098, 35922, 35606, 35565, 19242, 37596, 35734, 37158, 23211, 37077, 21810, 35274, 36043, 34125, 35662, 35397, 21867, 34101, 37468, 22187, 21706, 43092, 21675, 21803, 19110, 21290, 21163, 46407, 35558, 35442, 35189, 34149, 35495, 35220, 21835, 36051, 35110, 36147, 35428, 39660, 35930, 34197, 40250, 43149, 37268, 38157, 35534, 35421, 36530, 38133};
int T = 1;
cin >> T;
while (T--) {
int k;
cin >> k;
cout << -1 << '\n';
if (k == 1) {
cout << 0 << '\n';
continue;
}
for (int i = (32 - __builtin_clz(a[k])) - 1; i >= 0; i--)
cout << ((a[k] & (1 << i)) ? 1 : 0) << " ";
cout << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |