#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
#define N 1000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int T,n,ans,length,st[N+1],leng,cl[N+1],l[N+1],r[N+1],sl[N+1],sr[N+1],delta[N+1],delta2[N+1],dp[N+1][N+1],DP[N+1];
const int inf=(int)(1e9);
bool op,used[N+1],vis[N+1];
string s[N+1];
map<string,int>P;
vector<int>p[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
void dfs(int x,int rt)
{
    used[x]=1,p[rt].push_back(x);
    for (int i=0;i<E[x].size();++i)
    {
	if (!used[E[x][i]]) cl[E[x][i]]=cl[x]^1,dfs(E[x][i],rt);
	else if (cl[x]==cl[E[x][i]]) op=0;
    }
    return;
}
bool cmp(int x,int y)
{
    return sl[x]<sl[y];
}
void dfs2(int x)
{
    int maxn=0,maxn2=0;
    for (int i=0;i<ES[x].size();++i) dfs2(ES[x][i]);
    for (int i=1;i<=(n<<1);++i) delta[i]=delta2[i]=0;
    for (int i=0;i<p[x].size();++i)
    {
	if (!cl[p[x][i]])
	{
	    for (int j=l[p[x][i]];j<=r[p[x][i]];++j) delta[j]++;
	}
	else
	{
	    for (int j=l[p[x][i]];j<=r[p[x][i]];++j) delta2[j]++;
	}
    }
    for (int i=1;i<=(n<<1);++i) maxn=max(maxn,delta[i]),maxn2=max(maxn2,delta2[i]);
    //0
    for (int i=0;i<=n;++i) DP[i]=0;
    for (int i=0;i<ES[x].size();++i)
    {
	for (int j=0;j<=n;++j) st[j]=inf;
	for (int j=0;j+delta[l[ES[x][i]]]<=n;++j) st[j+delta[l[ES[x][i]]]]=dp[ES[x][i]][j]+delta2[l[ES[x][i]]];
	for (int j=1;j<=n;++j) st[j]=min(st[j],st[j-1]);
	for (int j=0;j<=n;++j) DP[j]=max(DP[j],st[j]);
    }
    for (int i=0;i<=maxn-1;++i) DP[i]=inf;
    for (int i=0;i<=n;++i) DP[i]=max(DP[i],maxn2),dp[x][i]=min(dp[x][i],DP[i]);
    //1
    for (int i=0;i<=n;++i) DP[i]=0;
    for (int i=0;i<ES[x].size();++i)
    {
	for (int j=0;j<=n;++j) st[j]=inf;
	for (int j=0;j+delta2[l[ES[x][i]]]<=n;++j) st[j+delta2[l[ES[x][i]]]]=dp[ES[x][i]][j]+delta[l[ES[x][i]]];
	for (int j=1;j<=n;++j) st[j]=min(st[j],st[j-1]);
	for (int j=0;j<=n;++j) DP[j]=max(DP[j],st[j]);
    }
    for (int i=0;i<=maxn2-1;++i) DP[i]=inf;
    for (int i=0;i<=n;++i) DP[i]=max(DP[i],maxn),dp[x][i]=min(dp[x][i],DP[i]);
    return;
}
int main()
{
    T=read();
    for (int i=1;i<=T;++i)
    {
	n=read(),P.clear(),length=leng=0,op=1,ans=inf;
	for (int j=1;j<=(n<<1);++j)
	{
	    cin>>s[j];
	    if (P.find(s[j])==P.end()) P[s[j]]=++length,l[length]=j;
	    else r[P[s[j]]]=j;
	}
	for (int j=0;j<=length;++j) p[j].clear(),E[j].clear(),ES[j].clear(),used[j]=vis[j]=0;
	for (int j=1;j<=length;++j)
	    for (int k=1;k<=length;++k)
		if (l[j]<l[k]&&l[k]<r[j]&&r[j]<r[k])
		    E[j].push_back(k),E[k].push_back(j);
	for (int j=1;j<=length;++j)
	    if (!used[j])
	    {
		cl[j]=0,dfs(j,j),sl[j]=inf,sr[j]=0;
		for (int k=0;k<p[j].size();++k) sl[j]=min(sl[j],l[p[j][k]]),sr[j]=max(sr[j],r[p[j][k]]);
		st[++leng]=j;
	    }
	if (!op)
	{
	    printf("Case #%d: -1\n",i);
	    continue;
	}
	sort(st+1,st+leng+1,cmp);
	for (int j=leng;j>=1;--j)
	    for (int k=j+1;k<=leng;++k)
		if (sr[st[k]]<sr[st[j]]&&!vis[st[k]])
		    ES[st[j]].push_back(st[k]),vis[st[k]]=1;
	for (int j=1;j<=leng;++j)
	    if (!vis[st[j]])
		ES[0].push_back(st[j]);
	for (int j=0;j<=length;++j)
	    for (int k=0;k<=n;++k)
		dp[j][k]=inf;
	dfs2(0);
	for (int i=0;i<=n;++i) ans=min(ans,i+dp[0][i]);
	printf("Case #%d: %d\n",i,ans);
    }
    return 0;
}