#include <bits/stdc++.h>

using namespace std;
const int N = 2e3 + 10,
dx[8][4] =
{ {0, 0, 1, 1},
{0, 0, 1, 2},
{0, 0, 1, 1},
{0, 0, 1, 2},
{0, 0, -1, -1},
{0, 0, -1, -2},
{0, 0, -1, -1},
{0, 0, -1, -2} },
dy[8][4] =
{ {0, 1, 0, 2},
{0, 1, 0, 1},
{0, -1, 0, -2},
{0, -1, 0, -1},
{0, -1, 0, -2},
{0, -1, 0, -1},
{0, 1, 0, 2},
{0, 1, 0, 1} },
M = 10;

int ansc[M][M][M] = {
{
{
0 }
},
{
{
0, 0 },
{
0, 0 }
},
{
{
1, 1, 2 },
{
1, 2, 1 },
{
0, 2, 2 }
},
{
{
1, 1, 2, 2 },
{
1, 2, 1, 2 },
{
3, 3, 4, 4 },
{
3, 4, 3, 4 }
},
{
{
1, 1, 0, 2, 2 },
{
1, 0, 1, 2, 4 },
{
3, 3, 5, 4, 2 },
{
3, 5, 3, 4, 4 },
{
0, 5, 5, 0, 0 }
},
{
{
1, 1, 0, 2, 2, 0 },
{
1, 0, 1, 2, 0, 2 },
{
3, 3, 4, 4, 5, 5 },
{
3, 4, 3, 4, 5, 8 },
{
6, 6, 7, 7, 8, 5 },
{
6, 7, 6, 7, 8, 8 }
},
{
{
1, 1, 0, 2, 2, 3, 3 },
{
1, 0, 1, 2, 3, 2, 3 },
{
4, 4, 7, 5, 5, 6, 6 },
{
4, 7, 4, 5, 6, 5, 6 },
{
0, 7, 7, 8, 8, 9, 9 },
{
10, 10, 11, 8, 11, 8, 9 },
{
10, 0, 10, 11, 11, 9, 0 }
},
{
{
1, 1, 2, 2, 3, 3, 4, 4 },
{
1, 2, 1, 2, 3, 4, 3, 4 },
{
5, 5, 6, 6, 7, 7, 8, 8 },
{
5, 6, 5, 6, 7, 8, 7, 8 },
{
9, 9, 10, 10, 11, 11, 12, 12 },
{
9, 10, 9, 10, 11, 12, 11, 12 },
{
13, 13, 14, 14, 15, 15, 16, 16 },
{
13, 14, 13, 14, 15, 16, 15, 16 }
},
{
{
1, 1, 2, 2, 3, 3, 7, 4, 4 },
{
1, 2, 1, 2, 3, 7, 3, 4, 10 },
{
5, 5, 6, 6, 0, 7, 7, 10, 4 },
{
5, 12, 6, 8, 8, 9, 9, 10, 10 },
{
12, 5, 8, 6, 8, 15, 9, 11, 11 },
{
12, 12, 13, 13, 15, 9, 16, 11, 16 },
{
14, 14, 13, 20, 15, 15, 16, 16, 11 },
{
14, 17, 17, 13, 20, 18, 18, 19, 19 },
{
17, 14, 17, 20, 20, 18, 19, 18, 19 }
}
}, ans[M] = {0, 0, 2, 4, 5, 8, 11, 16, 20};

int idx, T, a[N][N], c[M][M], idc[M];

int valid(int n, int x, int y, int k)
{
    for(int j = 0; j < 4; j++)
    {
        int nx = x + dx[k][j], ny = y + dy[k][j];
        if(nx <= 0 || ny <= 0 || nx > n || ny > n || c[nx][ny]) return 0;
    }
    return 1;
}

void ins0(int n, int x, int y, int k)
{
    ++idc[n];
    for(int j = 0; j < 4; j++)
    {
        int nx = x + dx[k][j], ny = y + dy[k][j];
        c[nx][ny] = idc[n];
    }
}

void del0(int n, int x, int y, int k)
{
    for(int j = 0; j < 4; j++)
    {
        int nx = x + dx[k][j], ny = y + dy[k][j];
        c[nx][ny] = 0;
    }
    --idc[n];
}


void dfs(int n, int x, int y)
{
    //cout << x << " " << y << endl;
    if((ans[n] - idc[n]) * 4 > n * n - ((x - 1) * n + y)) return;
    if(x > n)
    {
        if(idc[n] > ans[n])
        {
            ans[n] = idc[n];
            memcpy(ansc[n], c, sizeof(c));
        }
        return;
    }

    for(int k = 0; k < 8; k++)
    {
        if(valid(n, x, y, k))
        {
            ins0(n, x, y, k);
            dfs(n, x + (y == n), (y == n ? 1 : y + 1));
            del0(n, x, y, k);
        }
    }
    dfs(n, x + (y == n), (y == n ? 1 : y + 1));
}

void ins10(int x, int y)
{
    ++idx;
    a[x][y] = a[x][y + 1] = a[x + 1][y] = a[x + 1][y + 2] = idx;
    ++idx;
    a[x][y + 2] = a[x][y + 3] = a[x + 1][y + 1] = a[x + 1][y + 3] = idx;
}

void ins11(int x, int y)
{
    ++idx;
    a[x][y] = a[x][y + 1] = a[x + 1][y] = a[x + 2][y + 1] = idx;
    ++idx;
    a[x + 1][y + 1] = a[x + 2][y] = a[x + 3][y] = a[x + 3][y + 1] = idx;
}

void ins21(int x, int y)
{
    ++idx;
    a[x][y] = a[x][y + 1] = a[x + 1][y] = a[x + 1][y + 2] = idx;
    ++idx;
    a[x][y + 2] = a[x + 1][y + 1] = a[x + 2][y + 1] = a[x + 2][y + 2] = idx;
}

void ins22(int x, int y)
{
    ++idx;
    a[x][y] = a[x][y + 1] = a[x + 1][y + 1] = a[x + 2][y] = idx;
    ++idx;
    a[x + 1][y - 1] = a[x + 1][y] = a[x + 2][y - 1] = a[x + 2][y + 1] = idx;
}

void ins30(int x, int y)
{
    ++idx;
    a[x][y] = a[x][y + 1] = a[x + 1][y] = a[x + 2][y + 1] = idx;
    ++idx;
    a[x + 1][y + 1] = a[x + 3][y + 1] = a[x + 2][y + 2] = a[x + 3][y + 2] = idx;
}

void ins31(int x, int y)
{
    ++idx;
    a[x][y] = a[x][y + 1] = a[x + 1][y + 1] = a[x + 1][y - 1] = idx;
    ++idx;
    a[x + 1][y] = a[x + 1][y - 2] = a[x + 2][y - 2] = a[x + 2][y - 1] = idx;
}

void init()
{
    puts("{");
    for(int n = 1; n <= 9; n++)
    {
        memset(ansc[n], 0, sizeof(ansc[n])); ans[n] = 0;
        dfs(n, 1, 1);
        puts("{");
        for(int i = 1; i <= n; i++)
        {
            puts("{");
            for(int j = 1; j <= n; j++)
            {
                if(j < n) printf("%d, ", ansc[n][i][j]);
                else printf("%d ", ansc[n][i][j]);
            }
            if(i < n) puts("},");
            else puts("}");
        }
        if(n < 9) puts("},");
        else puts("}");
    }
    puts("}");
}

void solve1(int n, int x, int y)
{
    if(n == 9)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(ansc[n - 1][i - 1][j - 1]) a[x + i - 1][y + j - 1] = ansc[n - 1][i - 1][j - 1] + idx;
            }
        }
        idx += ans[n - 1];
        return;
    }
    for(int i = 1; i < n / 4; i++)
    {
        ins10(x, y + (i - 1) * 4);
        ins10(x + n - 2, y + (i - 1) * 4);
    }
    ins30(x, y + (n / 4 - 1) * 4);
    ins21(x, y + (n / 4 - 1) * 4 + 2);
    int m = n - 4, i;
    for(i = 4; i < n - 8; i += 4)
    {
        ins11(x + i, y + m);
        ins11(x + i - 1, y + m + 2);
    }
    //cout << endl << x + i - 1 << " " << y + m + 2 << endl;
    ins31(x + i - 1, y + m + 2);
    ins11(x + m, y + m + 2);
    ins22(x + n - 3, y + m);
    solve1(n - 4, x + 2, y);
}

void solve2(int n)
{
    if(n == 6)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(ansc[n - 1][i - 1][j - 1]) a[i][j] = ansc[n - 1][i - 1][j - 1] + idx;
            }
        }
        idx += ans[n - 1];
        return;
    }
    int m = n - 4;
    for(int i = 1; i <= n; i += 2)
    {
        ins10(i, m + 1);
    }
    for(int j = 1; j <= m; j += 2)
    {
        ins11(n - 3, j);
    }
    solve2(n - 4);
}

void solve3(int n)
{
    int m = n - 2;
    for(int i = 1; i < m; i += 4)
    {
        ins11(i, m + 1);
    }
    for(int j = 1; j < m; j += 4)
    {
        ins10(m + 1, j);
    }
    ins22(m, m + 1);
    solve1(n - 2, 1, 1);
}

int main()
{
    //freopen("data.out", "w", stdout);
    //init();
    //return 0;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                a[i][j] = 0;
            }
        }
        idx = 0;
        if(n % 4 == 0)
        {
            for(int i = 1; i <= n; i += 4)
            {
                for(int j = 1; j <= n; j += 4)
                {
                    ins10(i, j), ins10(i + 2, j);
                }
            }
        }
        else if(n % 4 == 1)
        {
            if(n >= 9) solve1(n, 1, 1);
            else
            {
                for(int i = 1; i <= n; i++)
                {
                    for(int j = 1; j <= n; j++)
                    {
                        a[i][j] = ansc[n - 1][i - 1][j - 1];
                    }
                }
                idx = ans[n - 1];
            }
        }
        else if(n % 4 == 2)
        {
            if(n >= 6) solve2(n);
            else
            {
                for(int i = 1; i <= n; i++)
                {
                    for(int j = 1; j <= n; j++)
                    {
                        a[i][j] = ansc[n - 1][i - 1][j - 1];
                    }
                }
                idx = ans[n - 1];
            }
        }
        else
        {
            if(n >= 11) solve3(n);
            else
            {
                for(int i = 1; i <= n; i++)
                {
                    for(int j = 1; j <= n; j++)
                    {
                        a[i][j] = ansc[n - 1][i - 1][j - 1];
                    }
                }
                idx = ans[n - 1];
            }
        }

        printf("%d\n", idx);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                printf("%d ", a[i][j]);
            }
            putchar('\n');
        }
    }
    return 0;
}