#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T &x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N = 2005;

int pattern[8][3][3] = {
    // 0
   {{1, 1, 0},
    {0, 1, 0},
    {1, 0, 0}},
    // 1
   {{1, 0, 1},
    {0, 1, 1},
    {0, 0, 0}},
    // 2
   {{0, 1, 0},
    {1, 0, 0},
    {1, 1, 0}},
    // 3
   {{1, 1, 0},
    {1, 0, 1},
    {0, 0, 0}},
    // 4
   {{1, 1, 0},
    {1, 0, 0},
    {0, 1, 0}},
    // 5
   {{0, 1, 1},
    {1, 0, 1},
    {0, 0, 0}},
    // 6
   {{1, 0, 0},
    {0, 1, 0},
    {1, 1, 0}},
    // 7
   {{1, 0, 1},
    {1, 1, 0},
    {0, 0, 0}},
};

int ans5[5][5] = {
{1, 0, 1, 2, 2},
{1, 1, 2, 3, 2},
{0, 0, 3, 4, 4},
{5, 5, 3, 3, 4},
{5, 0, 5, 4, 0}
};

int n;
int tot;
int vis[N][N];

inline void put(int id, int x, int y){
    ++tot;
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            if(pattern[id][i][j]){
                int px = x + i;
                int py = y + j;
                assert(0 <= px && px < n && 0 <= py && py < n);
                assert(!vis[px][py]);
                vis[px][py] = tot;
            }
        }
    }
    // for(int i = 0; i < n; ++i){
    //     for(int j = 0; j < n; ++j){
    //         printf("%d%c", vis[i][j], "\t\n"[j + 1 == n]);
    //     }
    // }
    // puts("---------------");
}

inline void put_type(int id, int x, int y){
    switch(id){
        case 1:{
            put(7, x, y);
            put(1, x, y + 1);
            break;
        }
        case 2:{
            put(4, x, y);
            put(2, x + 1, y);
            break;
        }
        case 3:{
            put(0, x, y + 1);
            put(3, x + 1, y);
            break;
        }
        case 4:{
            put(7, x, y);
            put(6, x, y + 1);
            break;
        }
        case 5:{
            put(2, x + 1, y);
            put(0, x, y + 1);
            break;
        }
        case 6:{
            put(3, x, y);
            put(1, x + 1, y + 1);
            break;
        }
    }
}

void dfs(int n, int x, int y){
    if(n <= 2) return;
    if(n % 4 == 0){
        for(int i = 0; i < n; i += 2){
            for(int j = 0; j < n; j += 4){
                put_type(1, x + i, y + j);
            }
        }
        return ;
    }
    if(n % 4 == 2){
        for(int i = 2; i < n; i += 4){
            put_type(2, x + i, y);
        }
        for(int j = 2; j < n; j += 4){
            put_type(1, x, y + j);
        }
        dfs(n - 2, x + 2, y + 2);
        return ;
    }
    if(n % 4 == 3){
        if(n == 3){
            put_type(3, x, y);
            return ;
        }
        dfs(n - 2, x, y);
        int k = n / 4;
        for(int i = 0; i < 4 * k; i += 4){
            put_type(1, x + 4 * k + 1, y + i);
        }
        for(int i = 0; i < 4 * k; i += 4){
            put_type(2, x + i, y + 4 * k + 1);
        }
        put_type(3, x + 4 * k, y + 4 * k);
        return ;
    }
    if(n % 4 == 1){
        if(n == 5){
            put(7, x, y);
            put(5, x, y + 2);
            put(2, x + 1, y + 2);
            put(0, x + 2, y + 3);
            put(3, x + 3, y);
            return ;
        }
        if(n == 9){
            put(1, x, y);
            put(2, x, y);
            put_type(1, x, y + 3);
            put_type(2, x, y + 7);
            put(7, x + 3, y);
            put(5, x + 2, y + 1);
            put_type(4, x + 2, y + 4);
            put(4, x + 4, y + 2);
            put(5, x + 5, y + 2);
            put(7, x + 5, y + 5);
            put(5, x + 4, y + 6);
            put_type(2, x + 5, y);
            put_type(1, x + 7, y + 2);
            put_type(3, x + 6, y + 6);
            return ;
        }
        dfs(n - 4, x + 2, y);
        int k = n / 4;
        for(int i = 0; i < 4 * k; i += 4){
            put_type(1, x, y + i);
        }
        put_type(4, x + 4 * k + 1, y);
        put_type(2, x + 4 * k + 4, y);
        for(int i = 0; i < 4 * k; i += 4){
            put_type(1, x + 2 + 4 * k, y + i);
        }
        put_type(5, x + 4 * k + 1, y + 4 * k);
        put_type(3, x + 4 * k + 2, y + 4 * k + 2);
        for(int i = 3; i < 4 * k; i += 2){
            put_type(6, x + i, y + 4 * k + 1);
        }
        return ;
    }
    assert(0);
}

inline void solve(){
    r(n);
    tot = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            vis[i][j] = 0;
        }
    }
    dfs(n, 0, 0);
    printf("%d\n", tot);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            printf("%d%c", vis[i][j], " \n"[j + 1 == n]);
        }
    }
}

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int T; r(T);
    while(T--){
        solve();
    }
    return 0;
}