#include <iostream>
#include <algorithm>
using namespace std;
int dp[30], t[30][2];
long long solve(int n, int mask) {
for (int i = 0; i <= n; i++) { t[i][0] = n; t[i][1] = n; dp[i] = 0; }
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) t[i][0] = i;
else t[i][1] = i;
}
for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < 2; j++) t[i][j] = min(t[i][j], t[i + 1][j]); }
dp[0] = 1;
for (int i = 0; i < n; i++) {
dp[t[i][0] + 1] += dp[i];
dp[t[i][1] + 1] += dp[i];
}
int sum = 0;
for (int i = 1; i <= n; i++) sum += dp[i];
return sum;
}
int len[1 << 20], num[1 << 20];
void search() {
for (int i = 1; i <= 20; i++) {
for (int j = 0; j < (1 << (i - 1)); j++) {
int G = solve(i, j);
if (len[G] == 0) { len[G] = i; num[G] = j; }
}
}
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int euler(int pos) {
int cnt = 0;
for (int i = 1; i <= pos; i++) {
if (gcd(i, pos) == 1) cnt++;
}
return cnt;
}
int main() {
search();
int T; cin >> T;
for (int i = 1; i <= T; i++) {
int A; cin >> A;
cout << euler(A + 2) << endl;
for (int j = 0; j < len[A]; j++) { if (j) cout << " "; cout << (num[A] / (1 << j)) % 2; } cout << endl;
}
return 0;
}
