RT，TLE了，会不会是输入出了问题？能给一组输入数据吗……

#include<bits/stdc++.h>

//#define TJ

using namespace std;

const int ND=17000,M=1100,N=4110,K=16;

char sr[20];
int ans,an[300];
int gr[20][20],sl[M],h[N],td;
int row[ND],col[ND],u[ND],d[ND],l[ND],r[ND];

void Build(int m){
	memset(h,-1,sizeof h);
	memset(sl,0,sizeof sl);
	for(register int i=0;i<=m;++i)
		u[i]=d[i]=i,l[i]=i-1,r[i]=i+1;
	l[0]=m,r[m]=0;
	td=m+1;
}

void New(int x,int y){
	if(~h[x])l[td]=h[x],r[td]=r[h[x]],l[r[td]]=td,r[h[x]]=td;
	else h[x]=l[td]=r[td]=td;
	row[td]=x,col[td]=y;
	u[td]=y,d[td]=d[y],u[d[td]]=td,d[y]=td;
	++td,++sl[y];
}

void Remove(int x){
	for(register int i=d[x];i!=x;i=d[i])
		for(register int j=r[i];j!=i;j=r[j])
			u[d[j]]=u[j],d[u[j]]=d[j],--sl[col[j]];
	l[r[x]]=l[x],r[l[x]]=r[x];
}

void Resume(int x){
	for(register int i=d[x];i!=x;i=d[i])
		for(register int j=r[i];j!=i;j=r[j])
			u[d[j]]=j,d[u[j]]=j,++sl[col[j]];
	l[r[x]]=x,r[l[x]]=x;
}

void Init(){
	for(register int i=0;i<K;++i){
		scanf("%s",sr);
		for(register int j=0;j<K;++j)
			if(sr[j]=='-')gr[i][j]=-1;
			else gr[i][j]=sr[j]-'A';
	}
//	for(register int i=0;i<K;++i){
//		for(register int j=0;j<K;++j)
//			printf("%d ",gr[i][j]);
//		puts("");
//	}
	for(register int i=0;i<K;++i)
		for(register int j=0;j<K;++j)
			if(!~gr[i][j])
				for(register int k=0;k<K;++k)
					New(i*K*K+j*K+k,i*K+k+1),New(i*K*K+j*K+k,K*K+j*K+k+1),New(i*K*K+j*K+k,2*K*K+(i/4*4+j/4)*K+k+1),New(i*K*K+j*K+k,3*K*K+i*K+j+1);
	for(register int i=0;i<K;++i)
		for(register int j=0;j<K;++j)
			if(~gr[i][j])
				Remove(i*K+gr[i][j]+1),Remove(K*K+j*K+gr[i][j]+1),Remove(2*K*K+(i/4*4+j/4)*K+gr[i][j]+1),Remove(3*K*K+i*K+j+1);
}

bool Dance(){
	if(!l[0])return 1;
	int x=r[0];
	for(register int i=r[r[0]];i;i=r[i])
		if(sl[i]<sl[x])x=i;
	Remove(x);
	for(register int i=d[x];i!=x;i=d[i]){
		an[ans++]=row[i];
		for(register int j=r[i];j!=i;j=r[j])Remove(col[j]);
		if(Dance())return 1;
		for(register int j=r[i];j!=i;j=r[j])Resume(col[j]);
		--ans;
	}
	Resume(x);
	return 0;
}

void Return(){
	for(register int i=0;i<ans;++i)gr[an[i]/K/K][an[i]/K%K]=an[i]%K;
}

void Print(){
	for(register int i=0;i<K;++i){
		for(register int j=0;j<K;++j)
			putchar(gr[i][j]+'A'); 
		puts("");
	}
}

int main(){
	#ifdef TJ
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	#endif
	int T;
	scanf("%d",&T);
	while(T--){
		ans=0;
		Build(1024);
		Init();
		Dance();
		Return();
		Print();
	}
	return 0;
}