#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
long long get_phi(int n) {
long long result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
int get_length(int a, int b) {
int length = 0;
while (a > 1 && b > 1) {
if (a > b) {
int count = (a - 1) / b;
length += count;
a -= count * b;
} else {
int count = (b - 1) / a;
length += count;
b -= count * a;
}
}
if (a > 1) length += (a - 1);
if (b > 1) length += (b - 1);
return length;
}
void print_shortest_string(int a, int b) {
vector<int> result;
while (a > 1 && b > 1) {
if (a > b) {
int count = (a - 1) / b;
for(int i=0; i<count; i++) result.push_back(0); // '0' ekle
a -= count * b;
} else {
int count = (b - 1) / a;
for(int i=0; i<count; i++) result.push_back(1); // '1' ekle
b -= count * a;
}
}
if (a > 1) {
for(int i=0; i < a - 1; i++) result.push_back(0);
}
if (b > 1) {
for(int i=0; i < b - 1; i++) result.push_back(1);
}
reverse(result.begin(), result.end());
for (int i = 0; i < result.size(); i++) {
cout << result[i] << (i == result.size() - 1 ? "" : " ");
}
cout << endl;
}
void solve() {
int K;
cin >> K;
long long count = get_phi(K + 2);
cout << count << endl;
int best_a = -1, best_b = -1;
int min_len = 2000000000;
for (int a = 1; a * 2 <= (K + 2); a++) {
int b = (K + 2) - a;
if (__gcd(a, b) == 1) {
int current_len = get_length(a, b);
if (current_len < min_len) {
min_len = current_len;
best_a = a;
best_b = b;
}
}
}
if (best_a != -1) {
print_shortest_string(best_a, best_b);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
if (cin >> T) {
while (T--) {
solve();
}
}
return 0;
}
