#include <cstdio>
#include <cstring>

#define CS			const static
#define INOUT(x,y)		freopen(x,"r",stdin) , freopen(y,"w",stdout)
#define Rep(x,l,r)		for(int x = (l) ; x <= (r) ; x++)
#define Rush(X)			int ____X , X ; scanf("%d",&____X) ; for(X = 1 ; X <= ____X ; X++)

CS int SQR[5] = { 1, 5,14,30,55} ;
CS int STK[5] = { 4,12,24,40,60} ;

CS int MaxM = 70 , MaxN = 65 , MaxT = MaxM * MaxN ;

int map[6][6][4] ;
int graph[MaxM][MaxN] ;

int X[MaxT] , Y[MaxT] , L[MaxT] , R[MaxT] , U[MaxT] , D[MaxT] ;
int SIZE[MaxN] , FY[MaxM] ;

bool vis[MaxN] , hash[MaxN] ;

int N , n , tot , m , ans ;

inline int min(int x,int y)	{return (x<y)?(x):(y);}
inline int max(int x,int y)	{return (x>y)?(x):(y);}

void Pretreat()
{
	memset(graph,0,sizeof(graph));

	Rep(i,1,N)
		Rep(j,1,N)
			map[i][j][0] = (i-1)*(2*N+1) + j ,
			map[i][j][1] = (i-1)*(2*N+1) + N + j ,
			map[i][j][2] = i * (2*N+1) + j ,
			map[i][j][3] = (i-1)*(2*N+1) + N + j + 1 ;

	int cal = 0 ;
	Rep(i,1,N)
		Rep(j,1,N)
		{
			int loop1 = min(N-i , N-j) + 1 ;
			Rep(k,1,loop1)
			{
				cal++ ;

				int loop2 = j+k-1 ;
				Rep(l,j,loop2)
				{
					int v = map[i][l][0] ;
					graph[v][++graph[v][0]] = cal ;
				}

				int loop3 = i+k-1 ;
				Rep(l,i,loop3)
				{
					int v = map[l][j][1] ;
					graph[v][++graph[v][0]] = cal ;
				}

				Rep(l,j,loop2)
				{
					int v = map[loop3][l][2] ;
					graph[v][++graph[v][0]] = cal ;
				}

				Rep(l,i,loop3)
				{
					int v = map[l][loop2][3] ;
					graph[v][++graph[v][0]] = cal ;
				}
			}
		}
}

void Link(int x,int y)
{
	SIZE[X[++tot] = x] ++ ; Y[tot] = y , U[tot] = U[x] ; D[tot] = x  ; U[D[tot]] = D[U[tot]] = tot ;
	if(FY[y]==-1)	FY[y] = L[tot] = R[tot] = tot ;
	else	L[tot] = L[FY[y]] , R[tot] = FY[y] , L[R[tot]] = R[L[tot]] = tot ;
}

void Cover(int c)	{for(int p = D[c] ; p != c ; p = D[p])	L[R[p]] = L[p] , R[L[p]] = R[p] ;}

void Resume(int c)	{for(int p = U[c] ; p != c ; p = U[p])	L[R[p]] = R[L[p]] = p ;}

void Build()
{
	memset(FY,-1,sizeof(FY)) ; memset(vis,0,sizeof(vis)) ;

	Rush(PTN)
	{
		int x ; scanf("%d",&x) ;
		Rep(i,1,graph[x][0])	vis[graph[x][i]] = true ;
	}

	tot = n = ans = SQR[N - 1] ;
	Rep(i,0,n)
		L[i] = i - 1 , R[i] = i + 1 , U[i] = D[i] = i ,
		X[i] = i , Y[i] = SIZE[i] = 0 ;
	L[0] = tot , R[tot] = 0 ;

	Rep(i,1,n)	if(vis[i])
		L[R[i]] = L[i] , R[L[i]] = R[i] ;

	Rep(i,1,STK[N-1])
		Rep(j,1,graph[i][0])	if(!vis[graph[i][j]])
			Link(graph[i][j],i) ;
}

int F()
{
	int ans = 0 ; memset(hash,0,sizeof(hash)) ;

	for(int p = R[0] ; p ; p = R[p])	if(!hash[p])
	{
		ans++ ; hash[p] = true ;
		for(int k = D[p] ; k != p ; k = D[k])
			for(int l = R[k] ; l != k ; l = R[l])	hash[X[l]] = true ;
	}

	return ans ;
}

void DLX(int dep)
{
	if(!R[0])	{ans = min(ans,dep) ; return ;}
	if(dep + F() >=ans)	return ;

	int c = - 1 , MINSIZE = 1000000 ;
	for(int p = R[0] ; p ; p = R[p])	if(SIZE[p]<MINSIZE)
		MINSIZE = SIZE[c = p] ;

	for(int p = D[c] ; p != c ; p = D[p])
	{
		Cover(p);
		for(int k = R[p] ; k != p ; k = R[k])	Cover(k) ;
		DLX(dep+1);
		for(int k = L[p] ; k != p ; k = L[k])	Resume(k) ;
		Resume(p);
	}
}

void Solve()
{
	scanf("%d",&N);

	Pretreat() , Build() ;

	DLX(0);

	printf("%d\n",ans) ;
}

int main()
{
	INOUT("data.in","data.out");

	Rush(T) Solve() ;

	return 0 ;
}

居然15ms过了，跪了啊，求神剪枝