#include<bits/stdc++.h>
using namespace std;
const int N=1005;
map<string, int> mp;
int a[N],n,m;
int l[N],r[N];
int fa[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int e2[N][N];
void merge(int x,int y){
	e2[x][y]=e2[y][x]=1;
	x=find(x),y=find(y);
	if(x!=y){
		fa[x]=y;
	}
}
int e[N][N];
int f[N][N],g[N][N];
int d[N];
int dfn[N],cnt;
int col[N];
void bfs(int p,int op){
	for(int i=1;i<=n;++i)
		col[i]=-1;
	col[p]=op;
	queue<int> q;
	q.push(p);
	while(!q.empty()){
		int p=q.front();
		q.pop();
		for(int i=1;i<=n;++i)
			if(e2[p][i]&&col[i]==-1){
				col[i]=col[p]^1;
				q.push(i);
			}
	}
}
void chkmin(int &x,int y){
	x=min(x,y);
}
void chkmax(int &x,int y){
	x=max(x,y);
}
int sum[N][N];
int qry(int lx,int ly,int rx,int ry){
	if(lx>ly||rx>ry)return 0;
	return sum[ly][ry]-sum[lx-1][ry]-sum[ly][rx-1]+sum[lx-1][rx-1];
}
void solve(int _){
	cin>>n;
	mp.clear(),m=0;
	for(int i=1;i<=n;++i)
		l[i]=r[i]=col[i]=dfn[i]=d[i]=0;
	cnt=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			e[i][j]=e2[i][j]=0;
	for(int i=1;i<=n*2;++i){
		string s;
		cin>>s;
		if(!mp[s])
			mp[s]=++m;
		a[i]=mp[s];
	}
	for(int i=1;i<=n*2;++i){
		if(!l[a[i]])l[a[i]]=i;
		else r[a[i]]=i;
	}
	for(int i=1;i<=2*n;++i)
		for(int j=1;j<=2*n;++j)
			sum[i][j]=0;
	for(int i=1;i<=n;++i)
		sum[l[i]][r[i]]++;
	for(int i=1;i<=2*n;++i)
		for(int j=1;j<=2*n;++j)
			sum[i][j]+=sum[i-1][j];
	for(int i=1;i<=2*n;++i)
		for(int j=1;j<=2*n;++j)
			sum[i][j]+=sum[i][j-1];
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			if(i==j)continue;
			int l1=l[i],r1=r[i];
			int l2=l[j],r2=r[j];
			if(l1>l2)swap(l1,l2),swap(r1,r2);
			if(l1<l2&&l2<r1&&r1<r2&&qry(l2+1,r1-1,r2+1,2*n)){
				printf("Case #%d: -1\n",_);
				return;
			}
		}
	for(int i=1;i<=n;++i)
		fa[i]=i;
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j){
			int l1=l[i],r1=r[i];
			int l2=l[j],r2=r[j];
			if(l1>l2)swap(l1,l2),swap(r1,r2);
			if(l2<r1&&r1<r2)
				merge(i,j);
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			if(i==j)continue;
			if(l[i]<=l[j]&&r[j]<=r[i]&&find(i)!=find(j))
				e[find(i)][find(j)]=1;
		}
	vector<int> rt;
	queue<int> q;
	for(int i=1;i<=n;++i)
		if(i==find(i))rt.push_back(i);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(e[i][j])d[j]++;
	for(int i=1;i<=n;++i)
		if(i==find(i)&&!d[i])q.push(i);
	while(!q.empty()){
		int p=q.front();
		q.pop();dfn[++cnt]=p;
		for(int i=1;i<=n;++i)
			if(e[p][i]){
				d[i]--;
				if(!d[i])q.push(i);
			}
	}
	for(int i=1;i<=n;++i)
		for(int j=0;j<=n;++j)
			f[i][j]=g[i][j]=0;
	for(int i=cnt;i>=1;--i){
		int p=dfn[i];
		vector<int> vet;
		for(int j=1;j<=n;++j)
			if(find(j)==p)
				vet.push_back(j);
		assert(vet.size()>0);
		int x=vet[0];
		//决策x取0/1
		bfs(x,0);

		for(int j=1;j<=n;++j)
			if(j==find(j)&&e[p][j]){
				int c0=0,c1=0;
				int L=l[j],R=r[j];
				for(int x:vet){
					if(l[x]<=L&&R<=r[x]){
						if(col[x]==0)c0++;
						else c1++;
					}
				}
				for(int k=0;k<=n;++k){
					int n0=k+c0;
					int n1=f[j][k]+c1;
					if(n0<=n)
						chkmax(f[p][n0],n1);
				}
			}
		int mx0=0,mx1=0;
		vector<int> b0(2*n+2),b1(2*n+2);
		for(int x:vet){
			if(col[x]==0)b0[l[x]]++,b0[r[x]+1]--;
			else b1[l[x]]++,b1[r[x]+1]--;
		}
		for(int i=1;i<=2*n;++i)
			b0[i]+=b0[i-1],b1[i]+=b1[i-1];
		for(int i=1;i<=2*n;++i){
			mx0=max(mx0,b0[i]);
			mx1=max(mx1,b1[i]);
		}
		for(int i=0;i<mx0;++i)
			f[p][i]=1e9;
		for(int i=mx0;i<=n;++i)
  			chkmax(f[p][i],mx1);
		bfs(x,1);
		for(int j=1;j<=n;++j)
			if(j==find(j)&&e[p][j]){
				int c0=0,c1=0;
				int L=l[j],R=r[j];
				for(int x:vet){
					if(l[x]<=L&&R<=r[x]){
						if(col[x]==0)c0++;
						else c1++;
					}
				}
				for(int k=0;k<=n;++k){
					int n0=k+c0;
					int n1=f[j][k]+c1;
					if(n0<=n)
						chkmax(g[p][n0],n1);
				}
			}
		mx0=0,mx1=0;
		vector<int> t0(2*n+2),t1(2*n+2);
		for(int x:vet){
			if(col[x]==0)t0[l[x]]++,t0[r[x]+1]--;
			else t1[l[x]]++,t1[r[x]+1]--;
		}
		for(int i=1;i<=2*n;++i)
			t0[i]+=t0[i-1],t1[i]+=t1[i-1];
		for(int i=1;i<=2*n;++i){
			mx0=max(mx0,t0[i]);
			mx1=max(mx1,t1[i]);
		}
		for(int i=0;i<mx0;++i)
			g[p][i]=1e9;
		for(int i=mx0;i<=n;++i)
  			chkmax(g[p][i],mx1);
		for(int j=n-1;j>=0;--j){
			chkmax(f[p][j],f[p][j+1]);
			chkmax(g[p][j],g[p][j+1]);
		}
		for(int j=0;j<=n;++j)
			chkmin(f[p][j],g[p][j]);
	}
	int ans=1e9;
	for(int i=0;i<=n;++i){
		int mx=0;
		for(int j=1;j<=n;++j)if(j==find(j))
			mx=max(mx,f[j][i]);
		ans=min(ans,mx+i);
	}
	printf("Case #%d: %d\n",_,ans);
}
int main(){
	int T;cin>>T;
	for(int i=1;i<=T;++i)
		solve(i);
}