#include<bits/stdc++.h>

using namespace std;

const int N = 500 + 5, Inf = 0x3f3f3f3f;

inline bool check(int l1, int r1, int l2, int r2){
	return (l1 < l2 && l2 < r1 && r1 < r2) || (l2 < l1 && l1 < r2 && r2 < r1);
}

inline void checkmin(int &x, int y){
	if(y < x) x = y;
}

inline void checkmax(int &x, int y){
	if(y > x) x = y;
}

class section{
public:
	int l, r;
	inline section() {}
	inline section(int l_, int r_){
		l = l_, r = r_;
	}
};

inline bool operator < (section s, section t){
	if(s.l != t.l) return s.l < t.l;
	else return s.r > t.r;
}

class bipartite{
public:
	vector<int> L, R;
	inline bipartite() {}
};

int n = 0, m = 0, dp[N][N] = {}, f[N][N] = {}, g[N][N] = {};
int tot = 0, bad = 0, col[N] = {}, ver[N] = {};
stack<int> st;
bipartite bip[N] = {};
section pos[N] = {}, sec[N] = {};
map<string, int> id;
vector<vector<int> > G(N), T(N);

inline void init(){
	memset(col, -1, sizeof(col)), bad = tot = 0;
	memset(dp, 0x3f, sizeof(dp)), memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));
	memset(ver, 0, sizeof(ver));
	stack<int>().swap(st);
	for(int i = 0 ; i < N ; i ++){
		bip[i] = bipartite();
		G[i].clear(), T[i].clear();
	}
	memset(pos, 0, sizeof(pos)), memset(sec, 0, sizeof(sec));
	map<string, int>().swap(id);
	n = m = 0;
}

inline void dfs(int u){
	if(col[u]) bip[m].R.push_back(u);
	else bip[m].L.push_back(u);
	for(int v : G[u]){
		if(col[v] == -1){
			col[v] = col[u] ^ 1;
			dfs(v);
		}
		else if(col[u] == col[v]) bad = 1;
	}
}

inline bool cmp(int u, int v){
	return sec[u] < sec[v];
}

inline int dep(int l, int r, vector<int> vec){
	int ret = 0;
	for(int id : vec){
		section s = pos[id];
		if(s.l < l && r < s.r) ret ++;
	}
	return ret;
}

inline int depx(vector<int> vec){
	int ret = 0;
	for(int i : vec){
		int d = 1;
		for(int j : vec) if(i != j){
			section s = pos[i], t = pos[j];
			if(t.l < s.l && s.r < t.r) d ++;
		}
		checkmax(ret, d);
	}
	return ret;
}

inline void work(int u){
	for(int v : T[u]){
		work(v);
		int Lx = dep(sec[v].l, sec[v].r, bip[u].L), Rx = dep(sec[v].l, sec[v].r, bip[u].R);
		for(int lim = 0 ; lim <= n ; lim ++){
			if(lim < Lx) checkmax(f[u][lim], Inf);
			else checkmax(f[u][lim], dp[v][lim - Lx] + Rx);
			if(lim < Rx) checkmax(g[u][lim], Inf);
			else checkmax(g[u][lim], dp[v][lim - Rx] + Lx);
		}
	}
	int Lx = depx(bip[u].L), Rx = depx(bip[u].R);
	for(int lim = 0 ; lim <= n ; lim ++){
			if(lim < Lx) checkmax(f[u][lim], Inf);
			else checkmax(f[u][lim], Rx);
			if(lim < Rx) checkmax(g[u][lim], Inf);
			else checkmax(g[u][lim], Lx);
		}
	for(int lim = 0 ; lim <= n ; lim ++){
		dp[u][lim] = min(f[u][lim], g[u][lim]);
		if(lim) checkmin(dp[u][lim], dp[u][lim - 1]);
	}
}

inline void solve(){
	cin >> n;
	string str = "";
	for(int i = 1 ; i <= 2 * n ; i ++){
		cin >> str;
		if(id[str]) pos[id[str]].r = i;
		else{
			id[str] = ++ tot;
			pos[tot].l = i;
		}
	}
	for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j < i ; j ++) if(check(pos[i].l, pos[i].r, pos[j].l, pos[j].r)){
		G[i].push_back(j);
		G[j].push_back(i);
	}
	for(int u = 1 ; u <= n ; u ++) if(col[u] == -1){
		m ++, col[u] = 0;
		dfs(u);
	}
	if(bad){
		cout << -1 << '\n';
		return;
	}
	sec[0] = section(0, 2 * n + 1);
	for(int u = 1 ; u <= m ; u ++){
		int l = Inf, r = -Inf;
		for(int i : bip[u].L) checkmin(l, pos[i].l), checkmax(r, pos[i].r);
		for(int i : bip[u].R) checkmin(l, pos[i].l), checkmax(r, pos[i].r);
		sec[u] = section(l, r), ver[u] = u;
	}
	sort(ver, ver + m + 1, cmp);
	st.push(0);
	for(int i = 1 ; i <= m ; i ++){
		int u = ver[i];
		while(sec[u].r > sec[st.top()].r) st.pop();
		T[st.top()].push_back(u), st.push(u);
	}
	work(0);
	int ans = Inf;
	for(int lim = 0 ; lim <= n ; lim ++) checkmin(ans, lim + dp[0][lim]);
	cout << ans << '\n';
}

int CASE = 0;

int main(){
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> CASE;
	for(int i = 1 ; i <= CASE ; i ++){
		cout << "Case #" << i << ": ";
		init(), solve();
	}
	
	return 0;
}