#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>
struct UnionFind {
vector<int> data;
UnionFind(int size) : data(size, -1) { }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
};
string solve1(string s, int n){//n ! 2n * 1
UnionFind uni(5000);
vector<bool> used(5000);
ll ans = 0, ecnt = 0;
REP(i, n * n){
if(s[i] == '0')ecnt++;
}
REP(i, n){
REP(j, n){
if(s[i * n + j] != '1')continue;
if(i != n - 1 and s[(i + 1) * n + j] == '1')uni.unionSet(i * n + j, (i + 1) * n + j);
if(j != n - 1 and s[i * n + j + 1] == '1')uni.unionSet(i * n + j, i * n + j + 1);
}
}
REP(i, n * n){
if(!used[uni.root(i)]){
used[uni.root(i)] = true;
ans++;
}
}
ans -= ecnt;
string res;
while(ans > 0){
if(ans % 2 == 1)res.push_back('1');
else res.push_back('0');
ans /= 2;
}
while(res.size() < 100) res.push_back('0');
return res;
}
P locate(ll x, ll y, ll n){
ll m = 2 * n + 1, fi = (m + 2)/ 3, se = m - fi * 2, I, J, X, Y;
if(x < fi) {
I = 0;
X = 0;
}
else if(x >= fi and x < fi * 2){
I = 1;
X = fi;
}
else {
I = 2;
X = fi * 2;
}
if(y < fi) {
J = 0;
Y = 0;
}
else if(y >= fi and y < fi * 2){
J = 1;
Y = fi;
}
else {
J = 2;
Y = fi * 2;
}
if(y < fi * 2){
return P(I * 3 + J, fi * (x - X) + (y - Y));
}
else{
return P(I * 3 + J, se * (x - X) + (y - Y));
}
}
string process(vector<vector<string>> a, int gi, int gj, int gk, int n){
ll m = 2 * n + 1, fi = (m + 2)/ 3, se = m - fi * 2;
if(gk < n - 1){//kousin
vector<vector<ll>> s(m, vector<ll>(m));//sim
REP(i, m){
ll I;
if(i < fi) I = 0;
else if(i >= fi and i < fi * 2)I = 1;
else I = 2;
REP(j, m){
ll J;
if(j < fi) J = 0;
else if(j >= fi and j < fi * 2)J = 1;
else J = 2;
s[i][j] = I * 3 + J + 1;
}
}
bool rok = false;
REP(kkk, n){
REP(i, m - 2 * (kkk + 1)){
REP(j, m - 2 * (kkk + 1)){
if(i == gi and j == gj and kkk == gk){
rok = true;
break;
}
ll nmin = 10;
REP(x, 3){
REP(y, 3){
if(s[i + x][j + y] > 0 and nmin > s[i + x][j + y]){
nmin = s[i + x][j + y];
}
}
}
if(nmin == 10)continue;
if(s[i][j] != 0)nmin = s[i][j];
REP(x, 3){
REP(y, 3){
if(x == 0 and y == 0)continue;
if(s[i + x][j + y] == nmin){
s[i + x][j + y] = 0;
}
}
}
s[i][j] = nmin;
}
if(rok)break;
}
if(rok)break;
}
//cout << gi << " " << gj << " " << gk << " !!!"<<endl;
//kousin
ll nmin = 10;
REP(x, 3){
REP(y, 3){
if(s[gi + x][gj + y] > 0 and nmin > s[gi + x][gj + y]){
nmin = s[gi + x][gj + y];
}
}
}
if(nmin == 10){//'0'
string res(100, '0');
return res;
}
if(s[gi][gj] != 0){
nmin = s[gi][gj];
if(gk == 0) swap(a[0][0][locate(gi, gj, n).second], a[0][0][0]);
}
else{
REP(d, 100) a[0][0][d] = '0';
}
REP(x, 3){
REP(y, 3){
if(x == 0 and y == 0)continue;
if(s[gi + x][gj + y] == nmin){
if(gk == 0) swap(a[x][y][locate(gi + x, gj + y, n).second], a[x][y][0]);
REP(d, 100) if(a[x][y][d] == '1')a[0][0][d] = '1';
}
}
}
//cout << a[0][0] <<endl;
return a[0][0];
}
else {//last
string mp;
REP(i, m){//init
REP(j, m){
P pos = locate(i, j, n);
mp.push_back(a[pos.first / 3][pos.first % 3][pos.second]);
//cout << i <<" " << j << " ! " << pos.first / 3 << " " << pos.first % 3 << " " << pos.second <<" " << a[pos.first / 3][pos.first % 3][pos.second]<<endl;
}
}
string res = solve1(mp, m);
return res;
}
}
