#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005
int t, n, cnt;
int ans[MAXN][MAXN];

int three[4][3][3] = {
                      {{0, 1, 1},
                      {2, 2, 1},
                      {2, 1, 2}},

                      {{1, 1, 0},
                      {1, 2, 2},
                      {2, 1, 2}},

                      {{1, 1, 2},
                      {1, 2, 1},
                      {0, 2, 2}},

                      {{1, 2, 1},
                      {2, 1, 1},
                      {2, 2, 0}},
                      };

int four[4][4] = {{1, 1, 2, 2},
                  {1, 2, 4, 3},
                  {3, 1, 3, 4},
                  {3, 3, 4, 4}};

int ver[2][4] = {{1, 1, 2, 2},
                 {1, 2, 1, 2}};
int hor[4][2] = {{1, 1},
                 {2, 1},
                 {1, 2},
                 {2, 2}};
int tmp[4][4][4] = {
                    {{1, 1, 0, 0},
                    {1, 2, 0, 0},
                    {0, 1, 2, 0},
                    {0, 2, 2, 0}},

                    {{0, 1, 1, 0},
                    {0, 2, 1, 0},
                    {2, 1, 0, 0},
                    {2, 2, 0, 0}},

                    {{1, 1, 0, 0},
                    {1, 2, 1, 2},
                    {0, 0, 2, 2},
                    {0, 0, 0, 0}},

                    {{0, 0, 2, 2},
                    {1, 2, 1, 2},
                    {1, 1, 0, 0},
                    {0, 0, 0, 0}},
                   
                   };

void place3(int x, int y, int d){
    for(int i=0;i<3;i++) for(int j=0;j<3;j++) 
        if(three[d][i][j]) ans[x+i][y+j] = cnt + three[d][i][j];
    cnt += 2;
}
void place4(int x, int y){
    for(int i=0;i<4;i++) for(int j=0;j<4;j++)
        ans[x+i][y+j] = cnt + four[i][j];
    cnt += 4;
}
void place24_ver(int x, int y){
    for(int i=0;i<2;i++) for(int j=0;j<4;j++)
        ans[x+i][y+j] = cnt + ver[i][j];
    cnt += 2;
}
void place24_hor(int x, int y){
    for(int i=0;i<4;i++) for(int j=0;j<2;j++)
        ans[x+i][y+j] = cnt + hor[i][j];
    cnt += 2;
}
void place24(int x, int y, int d){
    for(int i=0;i<4;i++) for(int j=0;j<4;j++) 
        if(tmp[d][i][j]) ans[x+i][y+j] = cnt + tmp[d][i][j];
    cnt += 2;
}

void solve0(int n){
    for(int i=1;i<=n;i+=4) for(int j=1;j<=n;j+=4) place4(i, j); 
}
void solve2(int n){
    solve0(n-2);
    int x = n/4*4+1;
    for(int i=1;i<=n-2;i+=4) place24_ver(x, i), place24_hor(i, x);
}
void solve1(int l, int r){
    if(r-l+1 == 9){
        place24_hor(1, l);
        place3(5, l, 1);
        place24_ver(8, l);
        place3(1, l+2, 3);
        place24(4, l+2, 0);
        place24_ver(1, l+5);
        place3(3, l+4, 1);
        place24_hor(3, l+7);
        place24(6, l+4, 1);
        place3(7, l+6, 0);
        return;
    }
    int len = r-l+1;
    for(int i=1;i<=n-5;i+=4) place24_hor(i, l), place24_hor(i, r-1);
    place24(len-4, l, 2);
    place3(len-2, l, 1);
    for(int i=l+4;i<=r-5;i+=4) place24_ver(len-3, i), place24_ver(len-1, i-1);
    place24(len-3, r-5, 1);
    place24_ver(len-1, r-3);
    place3(len-4, r-2, 0);
    solve1(l+2, r-2);
}
void solve3(int n){
    solve1(1, n-2);
    int x = n/4*4+2;
    for(int i=1;i<=n-3;i+=4) place24_ver(x, i), place24_hor(i, x);
    place3(n-2, n-2, 0);
}
void solve5(){
    place24_hor(1, 1);
    place3(1, 3, 0);
    ++cnt;
    ans[5][3] = ans[5][5] = ans[4][4] = ans[4][5] = cnt;
}
void solve7(){
    place3(1, 1, 3);
    place24_hor(4, 1);
    place24(1, 3, 1);
    place24_hor(1, 6);
    place3(5, 5, 0);
    ++cnt;
    ans[5][3] = ans[6][4] = ans[7][3] = ans[7][4] = cnt;
}

void work(){
    scanf("%d", &n);
    cnt = 0;
    if(n == 1) return (void)puts("0\n0");
    if(n == 2) return (void)puts("0\n0 0\n0 0\n");
    if(n == 3) place3(1, 1, 0);
    else if(n % 4 == 0) solve0(n);
    else if(n % 4 == 2) solve2(n);
    else if(n == 5) solve5();
    else if(n % 4 == 1) solve1(1, n);
    else if(n == 7) solve7();
    else if(n % 4 == 3) solve3(n);

    printf("%d\n", cnt);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c", ans[i][j], " \n"[j==n]);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j] = 0;
}
int main(){
    cin>>t;
    while(t--) work();
    return 0;
}