#include <bits/stdc++.h>

using namespace std;

using u32=unsigned int;
using i64=long long;
using u64=unsigned long long;
using db=double;
using vi=vector<int>;
using pii=pair<int,int>;

template<typename T>
T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch-'0'),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back

const int N=1010,INF=0x3f3f3f3f;

int n;
pii p[N];
vi e[N];

int bl[N],col[N],cnt;
pii rg[N];
bool dfs1(int x,int c,int b){
    bl[x]=b,col[x]=c;
    rg[b].fi=min(rg[b].fi,p[x].fi);
    rg[b].se=max(rg[b].se,p[x].se);
    bool ret=1;
    for(auto y:e[x]){
        if(!col[y]) ret&=dfs1(y,3-c,b);
        else if(col[y]==col[x]) ret=0;
    }
    return ret;
}

int f[N][N],g[N][N];
void dfs2(int x){
    vi ct,son;
    for(int i=1;i<=cnt;i++)
        if(rg[x].fi<rg[i].fi&&rg[i].se<rg[x].se) ct.pb(i);
    sort(ct.begin(),ct.end(),
        [&](int x,int y){return rg[x]<rg[y];});
    int lst=0;
    for(auto y:ct)
        if(lst<rg[y].fi) son.pb(y),lst=rg[y].se;
    for(auto y:son) dfs2(y);

    static int up[N],dw[N];
    for(int i=1;i<=2*n;i++) up[i]=dw[i]=0;
    for(int i=1;i<=n;i++){
        if(bl[i]==x){
            if(col[i]==1) up[p[i].fi]++,up[p[i].se+1]--;
            else dw[p[i].fi]++,dw[p[i].se+1]--;
        }
    }
    int mxu=0,mxd=0;
    for(int i=1;i<=2*n;i++){
        up[i]+=up[i-1],dw[i]+=dw[i-1];
        mxu=max(mxu,up[i]),mxd=max(mxd,dw[i]);
    }

    for(int i=0;i<=n;i++)
        f[x][i]=(i<mxu?INF:mxd),g[x][i]=(i<mxd?INF:mxu);
    for(auto y:son){
        int u=up[rg[y].fi],d=dw[rg[y].fi];
        for(int i=0;i<=n;i++){
            if(i>=u) f[x][i]=max(f[x][i],d+f[y][i-u]);
            if(i>=d) g[x][i]=max(g[x][i],u+f[y][i-d]);
        }
    }
    for(int i=0;i<=n;i++)
        f[x][i]=min(f[x][i],g[x][i]);
}

void clear(){
    cnt=0;
    for(int i=1;i<=n;i++)
        e[i].clear(),bl[i]=col[i]=0;
}

void solve(int id){
    cout<<"Case #"<<id<<": ";
    cin>>n;
    map<string,int> mp;
    for(int i=1,c=0;i<=2*n;i++){
        string s;cin>>s;
        auto it=mp.find(s);
        if(it==mp.end()) mp.insert({s,i});
        else p[++c]={it->se,i};
    }
    
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            if((p[i].fi<p[j].fi&&p[j].fi<p[i].se&&p[i].se<p[j].se)||
                (p[j].fi<p[i].fi&&p[i].fi<p[j].se&&p[j].se<p[i].se))
                e[i].pb(j),e[j].pb(i);
        }
    bool fl=1;
    for(int i=1;i<=n;i++)
        if(!col[i]){
            rg[++cnt]={2*n+1,0};
            fl&=dfs1(i,1,cnt);
        }
    if(!fl) return cout<<"-1"<<'\n',clear();
    rg[0]={0,2*n+1},dfs2(0);
    int ans=2*n;
    for(int i=0;i<=n;i++)
        ans=min(ans,i+f[0][i]);
    cout<<ans<<'\n',clear();
}

int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    int T;cin>>T;
    for(int i=1;i<=T;i++) solve(i);
    return 0;
}