#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int k;
cin >> k;
string ans;
int cnt = 0;
for (int i = 0; i <= k; i++) {
int x = i, y = k - i, sz = 0;
while (x || y) {
if (x > y) {
sz += x / (y + 1);
x %= (y + 1);
}
else if (x < y) {
sz += y / (x + 1);
y %= (x + 1);
}
else {
sz = -1;
break;
}
}
if (~sz) {
cnt++;
if (ans.empty() || sz < (int)ans.size()) {
ans.clear();
x = i; y = k - i;
while (x || y) {
if (x > y) {
for (int i = 0; i < x / (y + 1); i++)
ans += '1';
x %= (y + 1);
}
else if (x < y) {
for (int i = 0; i < y / (x + 1); i++)
ans += '0';
y %= (x + 1);
}
}
}
}
}
cout << cnt << '\n';
for (auto i : ans)
cout << i << ' ';
cout << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
}
