#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

int a[205][205];
int tileNumber = 1;

void solve3By2(int offsetI, int offsetJ)
{
    int mat[3][2] = {
        {1, 1},
        {2, 1},
        {2, 2}
    };

    for(int i = 0;i<3;i++)
        for(int j = 0;j<2;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 2;
}

void solve2By3(int offsetI, int offsetJ)
{
    int mat[2][3] = {
        {1, 1, 2},
        {1, 2, 2}
    };

    for(int i = 0;i<2;i++)
        for(int j = 0;j<3;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 2;
}

void solve6by2(int offsetI, int offsetJ)
{
    solve3By2(offsetI, offsetJ);
    solve3By2(offsetI+3, offsetJ);
}

void solve9by2(int offsetI, int offsetJ)
{
    solve3By2(offsetI, offsetJ);
    solve3By2(offsetI+3, offsetJ);
    solve3By2(offsetI+6, offsetJ);
}

void solve6by5(int offsetI, int offsetJ)
{
    int mat[6][5] = {
        {1, 2, 2, 3, 3},
        {1, 1, 2, 4, 3},
        {5, 6, 6, 4, 4},
        {5, 5, 6, 7, 7},
        {10, 9, 9, 8, 7},
        {10, 10, 9, 8, 8},
    };

    for(int i = 0;i<6;i++)
        for(int j = 0;j<5;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 10;
}

void solve9by5(int offsetI, int offsetJ)
{
    int mat[9][5] = {
        {1, 1, 2, 3, 3},
        {4, 1, 2, 2, 3},
        {4, 4, 5, 6, 6},
        {8, 5, 5, 7, 6},
        {8, 8, 7, 7, 9},
        {10, 11, 11, 9, 9},
        {10, 10, 11, 12, 12},
        {15, 13, 13, 14, 12},
        {15, 15, 13, 14, 14},
    };

    for(int i = 0;i<9;i++)
        for(int j = 0;j<5;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 15;
}

void solve4by4Minus(int offsetI, int offsetJ)
{
    int mat[4][4] = {
        {3, 3, 5, 0},
        {3, 1, 5, 5},
        {2, 1, 1, 4},
        {2, 2, 4, 4}
    };

    for(int i = 0;i<4;i++)
        for(int j = 0;j<4;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 5;
}

void solve7By7Minus(int offsetI, int offsetJ)
{
    int mat[7][7] = {
        {15,	15,	14,	13,	13,	1,	0},
        {16,	15,	14,	14,	13,	1,	1},
        {16,	16,	11,	11,	12,	2,	2},
        {10,	10,	11,	12,	12,	3,	2},
        {10,	8,	8,	6,	6,	3,	3},
        {9,	    8,	7,	6,	5,	4,	4},
        {9,	    9,	7,	7,	5,	5,	4}
    };

    for(int i = 0;i<7;i++)
        for(int j = 0;j<7;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 16;
}

void solve8By8Minus(int offsetI, int offsetJ)
{
    int mat[8][8] = {
        {1,	1,	2,	2,	5,	5,	12,	12},
        {1,	3,	3,	2,	6,	5,	13,	12},
        {0,	4,	3,	6,	6,	7,	13,	13},
        {11,4,	4,	10,	9,	7,	7,	8},
        {11,11,	10,	10,	9,	9,	8,	8},
        {21,21,	18,	18,	16,	16,	14,	14},
        {21,20,	19,	18,	17,	16,	15,	14},
        {20,20,	19,	19,	17,	17,	15,	15}
    };

    for(int i = 0;i<8;i++)
        for(int j = 0;j<8;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 21;
}

void solve1(int offsetI, int offsetJ, int n, int m)// 3j, m
{
    if(n>=6 && n%3==0)
    {
        for(int i = 0;i<n;)
        {
            if((n - i)%6!=0)
            {
                for(int j = 0;j<m;)
                {
                    if((m-j)%2!=0)
                    {
                        solve9by5(offsetI + i, offsetJ + j);
                        j += 5;
                    }
                    else
                    {
                        solve9by2(offsetI + i, offsetJ + j);
                        j += 2;
                    }
                }
                i += 9;
            }
            else
            {
                for(int j = 0;j<m;)
                {
                    if((m-j)%2!=0)
                    {
                        solve6by5(offsetI + i, offsetJ + j);
                        j += 5;
                    }
                    else
                    {
                        solve6by2(offsetI + i, offsetJ + j);
                        j += 2;
                    }
                }
                i += 6;
            }
        }
    }
}

void solve2(int offsetI, int offsetJ, int n, int m) //4, 3k
{
    for(int j = 0;j<m;j+=3)
    {
        solve2By3(offsetI, offsetJ+j);
        solve2By3(offsetI+2, offsetJ+j);
    }
}

void solve3(int offsetI, int offsetJ, int n, int m) //3k, 2
{
    for(int i = 0;i<n;i+=3)
    {
        solve3By2(offsetI+i, offsetJ);
    }
}

void solve4(int offsetI, int offsetJ, int n, int m) //2, 3k
{
    for(int j = 0;j<m;j+=3)
    {
        solve2By3(offsetI, offsetJ+j);
    }
}

void solve2By2Minus(int offsetI, int offsetJ)
{
    int mat[2][2] = {
        {1, 0},
        {1, 1}
    };

    for(int i = 0;i<2;i++)
        for(int j = 0;j<2;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 1;
}

void solve5By5Minus(int offsetI, int offsetJ)
{
    int mat[5][5] = {
        {8,	8,	2,	2,	0},
        {8,	7,	2,	1,	1},
        {7,	7,	4,	4,	1},
        {6,	6,	5,	4,	3},
        {6,	5,	5,	3,	3}
    };

    for(int i = 0;i<5;i++)
        for(int j = 0;j<5;j++)
            if(mat[i][j]!=0) a[offsetI+i][offsetJ+j] = mat[i][j] + tileNumber;

    tileNumber += 8;
}

ifstream fin("figures.in");
ofstream fout("figures.out");

#ifdef __LOCAL__
    #define fin cin
    #define fout cout
#endif // __LOCAL__

void solveTestcase()
{
    tileNumber = 0;
    memset(a, 0, sizeof(a));

    int n;
    fin >> n;

    if(n==1)
    {
        fout << "0" << '\n';
        fout << "0" << '\n';
    }
    else if(n==2)
    {
        fout << "1" << '\n';
        fout << "1 0" << '\n';
        fout << "1 1" << '\n';
    }
    else if(n==3)
    {
        fout << "2" << '\n';
        fout << "1 2 2" << '\n';
        fout << "1 1 2" << '\n';
        fout << "0 0 0" << '\n';
    }
    else if(n==5)
    {
        solve5By5Minus(0, 0);

        fout << "8" << '\n';
        for(int i = 0;i<n;i++)
        {
            fout << a[i][0];
            for(int j = 1;j<n;j++) fout << " " << a[i][j];
            fout << '\n';
        }
    }
    else if(n==7)
    {
        solve7By7Minus(0, 0);

        fout << "16" << '\n';
        for(int i = 0;i<n;i++)
        {
            fout << a[i][0];
            for(int j = 1;j<n;j++) fout << " " << a[i][j];
            fout << '\n';
        }
    }
    else if(n==8)
    {
        solve8By8Minus(0, 0);

        fout << "21" << '\n';
        for(int i = 0;i<n;i++)
        {
            fout << a[i][0];
            for(int j = 1;j<n;j++) fout << " " << a[i][j];
            fout << '\n';
        }
    }
    else if(n%3==1)
    {
        solve2(0, 0, 4, (n-4));
        solve1(4, 0, (n-4), n);
        solve4by4Minus(0, (n-4));

        fout << (n*n - 1)/3 << '\n';
        for(int i = 0;i<n;i++)
        {
            fout << a[i][0];
            for(int j = 1;j<n;j++) fout << " " << a[i][j];
            fout << '\n';
        }
    }
    else if(n%3==2)
    {
        solve1(0, 0, n-2, n-2);
        solve3(0, n-2, n-2, 2);
        solve4(n-2, 0, 2, n-2);
        solve2By2Minus(n-2, n-2);

        fout << (n*n - 1)/3 << '\n';
        for(int i = 0;i<n;i++)
        {
            fout << a[i][0];
            for(int j = 1;j<n;j++) fout << " " << a[i][j];
            fout << '\n';
        }
    }
    else if(n%3==0)
    {
        solve1(0, 0, n, n);

        fout << n*n/3 << '\n';
        for(int i = 0;i<n;i++)
        {
            fout << a[i][0];
            for(int j = 1;j<n;j++) fout << " " << a[i][j];
            fout << '\n';
        }
    }
}

int main()
{
    int T;
    fin >> T;

    while(T--)
        solveTestcase();
}