XOR grid thinking

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

constexpr int INF = (int)2e18;
constexpr int N = (int)2e5 + 111;
constexpr int md = (int)998244353;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr double eps = 1e-7;

typedef __int128 _uint;
typedef long long ll;

mt19937_64 rnd(time(nullptr));

void add(int& a,int b){
    a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b; while(a < 0) a += md;
}
void add(__int128& a,int b){
    a += b;
}
void sub(__int128& a,int b){
    a -= b;
}

int bpow(int a,int b){
    if(b == 0)
        return 1;
    if(b % 2 == 0){
        int t = bpow(a,b>>1);
        return 1ll*t*t%md;
    }
    return 1ll * a*bpow(a,b-1) % md;
}

int inv(int a){
    return bpow(a,md-2);
}

int fac[N],invfac[N];

void init(){
    fac[0] = 1;
    for(int i = 1; i < N; i++){
        fac[i] = (fac[i-1] * i) % md;
    }
    invfac[N-1] = inv(fac[N-1]);
    for(int i = N-2; i >= 0; i--){
        invfac[i] = (invfac[i+1] * (i+1))%md;
    }
    return;
}

int C(int n,int k){
    if(k > n)
        return 0;
    return fac[n] * invfac[k] % md * invfac[n-k] % md;
}

int A(int n,int k){
    if(k > n)
        return 0;
    return fac[n] * invfac[n-k] % md;
}
int g[1111][1111];
int n;
string to_binary(int x){
    string s = "";
    for(int i = 0; i < n*n; i++){
        s += (char)((x >> i & 1) + '0');
    }
    return s;
}
int getBits(int r){
    if(r == 0)
        return 0;
    return (1 << (r+1)) - 1;
}
int getBits(int l,int r){
    return getBits(r) ^ getBits(l-1);
}

void solve(){
    cin >> n;

    int c = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            g[i][j] = (1ll << c);
            c++;
        }
    }

    int a[n+2][n+2];

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = g[i][j-1] ^ g[i][j+1] ^ g[i+1][j] ^ g[i-1][j];
        }
    }

    int x = 0;

    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n; j++){
            if(i % 2 == 0 && (j % 4 < 2))
                continue;
            x ^= a[i][j];
        }
        cout << to_binary(x) << "\n";
    }
//    assert(x == (1 << (n*n)) - 1);
//    return;

    int mask = 0;
    for(int mask = 0; mask < (1ll << (n*5)); mask = (mask + 1) | ((1ll << n) - 1)){
        int x = 0;
        c = 0;
        mask |= (1ll << n) - 1;
        mask |= getBits(n+1,2*n-2);
        vector<pair<int,int>> p;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(mask >> c & 1){
                    x ^= a[i][j];
                    p.pb(mp(i,j));
                }
                c++;
            }
        }
//        cerr << "mask = " << mask << "\n";
        if((x & ((1ll << (4*n)) - 1)) == (1ll<<(4*n))-1){
            cout << "x = " << to_binary(x) << "\n";
            cout << p.size() << "\n";
            for(auto&[x,y] : p){
                cout << x << " " << y << "\n";
            }
            cout.flush();
        }
    }

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    init();
    int tests = 1;
    cin >> tests;
    for(int test = 1; test <= tests; test++){
//        cerr << "test = " << test << "\n";
        solve();
    }
    return 0;
}
/**
1: k,2k,3k,4k ...
2: k+(k+1),k+2(k+1),k+3(k+1)..., 2k+(k+1), 2k+2(k+1)

1
6
100001111111000000000000000000000000
111000000001011001000000000000000000
111000111110111000111111000000000000
111000111110100001000001011001000000
111000111110100001111110111000111111
x = 111111111111111111111111111111111111
24
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
3 1
3 2
3 5
3 6
4 2
4 3
4 4
4 5
5 1
5 2
5 3
5 4
5 5
5 6

**/