根据题意模拟即可

//
//  main.cpp
//  zoj1788
//
//  Created by cfhaiteeh on 13/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1234567;
struct he{
    int x1,y1,x2,y2;
};
int ai[maxn];
int mat[513][513];
int T,n;
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mat[i][j]);
}
int st;
bool getCmp(int x1,int y1,int x2,int y2){
     int cmp=mat[x1][y1];
    for(int i=x1;i<=x2;i++){
        for(int j=y1;j<=y2;j++){
            if(mat[i][j]!=cmp)return 0;
        }
    }
    return 1;
}
queue<he> Q;
void pushQ(int x1,int x2,int y1,int y2){
  
    he c;
    c.x1=x1;
    c.x2=x2;
    c.y1=y1;
    c.y2=y2;
    Q.push(c);
}
void BFS(){
    he fir;
    fir.x1=1;
    fir.y1=1;
    fir.x2=n;
    fir.y2=n;
    st=0;
    Q.push(fir);
    while(!Q.empty()){
        he c=Q.front();
        Q.pop();
        bool flag=getCmp(c.x1, c.y1, c.x2, c.y2);
        if(flag){
            ai[++st]=0;
            ai[++st]=mat[c.x1][c.y1];
        }
        else{
            ai[++st]=1;
            int mid1=(c.x1+c.x2)/2;
            int mid2=(c.y1+c.y2)/2;
            pushQ(c.x1, mid1, c.y1, mid2);
            pushQ(c.x1,mid1,mid2+1,c.y2);
            pushQ(mid1+1, c.x2, c.y1, mid2);
            pushQ(mid1+1,c.x2,mid2+1,c.y2);
        }
       
    }
}
char ans[maxn];
int ci[]={1,2,4,8};
char getChar(int t){
    int s=0;
    for(int i=0;i<4;i++){
        s=s+ai[t]*ci[i];
        t--;
        if(t==0)break;
    }
    if(s>10){
        s-=10;
        return s+'A';
    }
    return s+'0';
}
int now;
void play(){
    if(!Q.empty()){
        Q.pop();
    }
    BFS();
    now=0;
    for(int i=st;i>=1;i-=4){
        ans[++now]=getChar(i);
        
    }
}
void pri(){
    for(int i=now;i>=1;i--)printf("%c",ans[i]);
    printf("\n");
}
int main() {
    // insert code here...
    scanf("%d",&T);
    while(T--){
        init();
        play();
        pri();
    }
    return 0;
}