/*
    author:  Maksim1744
    created: 25.11.2023 14:18:46
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
//     return b == 0 ? a : gcd(b, a % b);
// });

template<size_t N>
bool operator < (const bitset<N>& a, const bitset<N>& b) {
    if (a == b) return false;
    int ind = (a ^ b)._Find_first();
    return b.test(ind);
}

struct Cmp {
    template<size_t N>
    bool operator () (const bitset<N>& a, const bitset<N>& b) const {
        if (a == b) return false;
        int ind = (a ^ b)._Find_first();
        return b.test(ind);
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    vector<vector<string>> preps = {
        vector<string>{
            ".AA",
            "BAB",
            "BBA",
        },
        vector<string>{
            "..AA.",
            "BBACC",
            ".BCAC",
            "BDDEE",
            ".DEDE",
        },
        vector<string>{
            ".A.ABB.",
            "CCAABDD",
            "CECEDBD",
            ".EEFFGG",
            "HH.FGFG",
            "HIIJJKK",
            "IHIJKJK",
        },
        vector<string>{
            ".AABBCCDD",
            "EEABCBCDF",
            "EAGGHHIFD",
            "JEJGHIHFF",
            "JJGKKIILL",
            "MMKNKNOLO",
            "MPQQNNOOL",
            "PMQRRSSTT",
            "PPRQRSTST",
        },
        vector<string>{
            "ABACCDEEFFGGH",
            "BAACDCEFEFGHG",
            "BBIIDDJJKKLHH",
            "MIMINJNJKLKOO",
            "MMPQPNNRRLLOS",
            "TTQPPUURVRVSO",
            "TWQQXXUYYVVSS",
            "WTZZXU[Y[//]]",
            "WWZ^^X[[Y/]/]",
            "__^Z^``aabbcc",
            "_dee.`a`abcbc",
            "d_effgghhiijj",
            "ddfefghghijij",
        },
        vector<string>{
            "ABAB",
            "AABB",
        },
        vector<string>{
            "AA",
            "AB",
            "BA",
            "BB",
        },
    };

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        int last = 0;
        vector<vector<int>> v(n, vector<int>(n, 0));

        auto fill_at = [&](int i, int j, int n, int m) {
            assert(i + n <= v.size());
            assert(j + m <= v.size());
            for (const auto& prep : preps) {
                if (prep.size() == n && prep[0].size() == m) {
                    map<char, int> who;
                    for (int x = 0; x < n; ++x) {
                        for (int y = 0; y < m; ++y) {
                            if (prep[x][y] == '.') continue;
                            if (!who.count(prep[x][y])) {
                                ++last;
                                who[prep[x][y]] = last;
                            }
                            assert(v[x + i][y + j] == 0);
                            v[x + i][y + j] = who[prep[x][y]];
                        }
                    }
                    return;
                }
            }
            assert(false);
        };

        auto fill_even = [&](int i, int j, int n, int m) {
            assert(n % 2 == 0);
            assert(m % 2 == 0);
            if (n % 4 == 0) {
                for (int x = 0; x < n; x += 4)
                    for (int y = 0; y < m; y += 2)
                        fill_at(i+x, y+j, 4, 2);
            } else {
                assert(m % 4 == 0);
                for (int x = 0; x < n; x += 2)
                    for (int y = 0; y < m; y += 4)
                        fill_at(i+x, y+j, 2, 4);
            }
        };

        if (n % 2 == 0) {
            if (n % 4 == 0) {
                for (int i = 0; i < n; i += 2) {
                    for (int j = 0; j < n; j += 4) {
                        fill_at(i, j, 2, 4);
                    }
                }
            } else {
                for (int i = 0; i < n; i += 2) {
                    for (int j = 0; j + 4 <= n; j += 4) {
                        fill_at(i, j, 2, 4);
                    }
                }
                for (int i = 0; i + 4 <= n; i += 4) {
                    fill_at(i, n - 2, 4, 2);
                }
            }
        } else {
            if (n == 1) {
            } else if (n == 3 || n == 5 || n == 7) {
                fill_at(0, 0, n, n);
            } else {
                auto start_from = (n % 8 < 4 ? 9 : 13);
                int k = start_from;
                fill_at(0, 0, k, k);
                while (k + 8 <= n) {
                    fill_at(k-1, k-1, 9, 9);
                    fill_even(k, 0, 8, k-1);
                    fill_even(0, k, k-1, 8);
                    k += 8;
                }
                if (k != n) {
                    fill_at(k-1, k-1, 3, 3);
                    for (int i = 0; i + 4 <= k; i += 4) {
                        fill_at(i, k, 4, 2);
                        fill_at(k, i, 2, 4);
                    }
                }
            }
        }

        cout << last << '\n';
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << v[i][j] << " \n"[j + 1 == n];
            }
        }
        #ifdef HOUSE
        vector<int> cnt(last);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (v[i][j] != 0)
                    cnt[v[i][j] - 1]++;
            }
        }
        assert(count(cnt.begin(), cnt.end(), 4) == cnt.size());
        cout.flush();
        #endif
    }

    // const int n = 7;
    // const int m = 7;
    // static_assert(n >= 4);
    // static_assert(m >= 4);
    // using B = bitset<n * m>;

    // auto ind = [&](int i, int j) {
    //     return i * m + j;
    // };

    // vector<B> base;
    // {
    //     B square = 0;
    //     square.set(ind(1, 1));
    //     square.set(ind(1, 2));
    //     square.set(ind(2, 1));
    //     square.set(ind(2, 2));
    //     {
    //         auto u = square;
    //         u.flip(ind(1, 1));
    //         u.flip(ind(0, 1));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(1, 1));
    //         u.flip(ind(1, 0));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(1, 2));
    //         u.flip(ind(1, 3));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(1, 2));
    //         u.flip(ind(0, 2));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(2, 1));
    //         u.flip(ind(2, 0));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(2, 1));
    //         u.flip(ind(3, 1));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(2, 2));
    //         u.flip(ind(2, 3));
    //         base.pb(u);
    //     }
    //     {
    //         auto u = square;
    //         u.flip(ind(2, 2));
    //         u.flip(ind(3, 2));
    //         base.pb(u);
    //     }
    // }

    // for (auto& x : base) {
    //     while ((x >> m).count() == 4) x >>= m;
    //     while (true) {
    //         bool ok = true;
    //         for (int i = 0; i < n; ++i) {
    //             if (x[ind(i, 0)]) {
    //                 ok = false;
    //                 break;
    //             }
    //         }
    //         if (ok) x >>= 1;
    //         else break;
    //     }
    // }

    // // auto print = [&](const B& b) {
    // //     for (int i = 0; i < n; ++i) {
    // //         for (int j = 0; j < n; ++j) {
    // //             cout << ".#"[b[ind(i, j)]];
    // //         }
    // //         cout << '\n';
    // //     }
    // //     cout << endl;
    // // };

    // sort(base.begin(), base.end());
    // base.erase(unique(base.begin(), base.end()), base.end());

    // vector<B> v;
    // for (auto b : base) {
    //     while (true) {
    //         v.pb(b);
    //         if ((b << m).count() != 4) break;
    //         b <<= m;
    //     }
    // }
    // swap(v, base);
    // v.clear();

    // for (auto b : base) {
    //     while (true) {
    //         v.pb(b);
    //         bool ok = true;
    //         for (int i = 0; i < n; ++i) {
    //             if (b.test(ind(i, m-1))) {
    //                 ok = false;
    //                 break;
    //             }
    //         }
    //         if (!ok) break;
    //         b <<= 1;
    //     }
    // }

    // swap(v, base);

    // sort(base.begin(), base.end());

    // // for (auto& x : base)
    // //     print(x);

    // int best = 0;

    // map<B, B, Cmp> par;
    // vector<B> suf = base;
    // for (int i = (int)suf.size() - 2; i >= 0; --i)
    //     suf[i] |= suf[i + 1];
    // best = 0;

    // y_combinator([&](auto dfs, B mask, int i) -> void {
    //     // if (mask.test(0)) return;
    //     if (mask.count() > best) {
    //         best = mask.count();
    //         cout << "new best: " << best << ", empty: " << mask.size() - mask.count() << endl;
    //         auto ms = mask;
    //         char c = 'A';
    //         vector<string> field(n, string(m, '.'));
    //         while (ms.count()) {
    //             auto here = ms ^ par[ms];
    //             for (int i = 0; i < n; ++i) {
    //                 for (int j = 0; j < m; ++j) {
    //                     if (here.test(ind(i, j))) {
    //                         field[i][j] = c;
    //                     }
    //                 }
    //             }
    //             ++c;
    //             ms ^= here;
    //         }
    //         for (auto s : field) {
    //             cout << s << endl;
    //         }
    //     }
    //     if (i == base.size()) return;
    //     if ((mask | suf[i]).count() <= best) return;
    //     B other = 0;
    //     for (int j = i; j < base.size(); ++j)
    //         if ((mask & base[j]).count() == 0)
    //             other |= base[j];
    //     if ((mask | other).count() <= best) return;
    //     if ((mask & base[i]).count() == 0 && !par.count(mask | base[i])) {
    //         par[mask | base[i]] = mask;
    //         dfs(mask | base[i], i + 1);
    //     }
    //     dfs(mask, i + 1);
    // })(B{0}, 0);

    return 0;
}