Note this is very optimized for speed, you don't actually need to optimize the constant this much to get AC.

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 5005;
 
unsigned char dp1[MAXN][MAXN];
unsigned char dp2[MAXN][MAXN];
 
unsigned char base_cell(int i, int j, int n) {
    return (i + j <= n - 1) && ((i - j) % 3 != 0);
}
 
void cook(int n) {
    for (int i = 0; i < n; ++i) {
        memset(dp1[i], 0, n * sizeof(dp1[i][0]));
        memset(dp2[i], 0, n * sizeof(dp2[i][0]));
    }
 
    for (int i = 0; i < n; ++i) {
        int j = n - 1 - i;
        if (base_cell(i, j, n)) continue;
 
        if (i < n / 2) {
            if (i > 0) dp1[i - 1][j] ^= 1;
        } else {
            if (j > 0) dp2[i][j - 1] ^= 1;
        }
    }
 
    for (int i = n - 1; i >= 1; --i) {
        for (int j = 0; j < n; ++j) {
            if (!dp1[i][j]) continue;
            dp1[i - 1][j] ^= 1;
            if (j + 1 < n) dp1[i - 1][j + 1] ^= 1;
        }
    }
 
    for (int j = n - 1; j >= 1; --j) {
        for (int i = 0; i < n; ++i) {
            if (!dp2[i][j]) continue;
            dp2[i][j - 1] ^= 1;
            if (i + 1 < n) dp2[i + 1][j - 1] ^= 1;
        }
    }
 
    string row;
 
    for (int i = n - 1; i >= 0; --i) {
        row.clear();
        for (int j = n - 1; j >= 0; --j) {
            unsigned char val = base_cell(i, j, n);
 
            if (i + j == n - 1 && !val) val = 1;
 
            val ^= dp1[i][j] ^ dp2[i][j];
 
            row.push_back(char('0' + val));
            row.push_back(' ');
        }
        row.push_back('\n');
        cout << row;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cook(n);
    }
    return 0;
}