Problem: Snuke has found two trees A and B, each with N vertices numbered 1 to N. The i-th edge of A connects Vertex a_i and b_i, and the j-th edge of B connects Vertex c_j and d_j. Also, all vertices of A are initially painted white.

Snuke would like to perform the following operation on A zero or more times so that A coincides with B:

* Choose a leaf vertex that is painted white. (Let this vertex be v.)
* Remove the edge incident to v, and add a new edge that connects v to another vertex.
* Paint v black.



Determine if A can be made to coincide with B, ignoring color. If the answer is yes, find the minimum number of operations required.

You are given T cases of this kind. Find the answer for each of them.

Constraints

* 1 \leq T \leq 20
* 3 \leq N \leq 50
* 1 \leq a_i,b_i,c_i,d_i \leq N
* All given graphs are trees.

Input

Input is given from Standard Input in the following format:


T
case_1
:
case_{T}


Each case is given in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

For each case, if A can be made to coincide with B ignoring color, print the minimum number of operations required, and print `-1` if it cannot.

Examples

Input

2
3
1 2
2 3
1 3
3 2
6
1 2
2 3
3 4
4 5
5 6
1 2
2 4
4 3
3 5
5 6


Output

1
-1


Input

3
8
2 7
4 8
8 6
7 1
7 3
5 7
7 8
4 2
5 2
1 2
8 1
3 2
2 6
2 7
4
1 2
2 3
3 4
3 4
2 1
3 2
9
5 3
4 3
9 3
6 8
2 3
1 3
3 8
1 7
4 1
2 8
9 6
3 6
3 5
1 8
9 7
1 6


Output

6
0
7

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=55;
const int INF=N;
int n,ans;
int a[N][N],b[N][N];
int fa[N],fb[N];
vector <int> e[N];
void dfsa(int x,int pre){
	fa[x]=pre;
	For(i,1,n)
		if (a[x][i]&&i!=pre)
			dfsa(i,x);
}
void dfsb(int x,int pre){
	fb[x]=pre;
	For(i,1,n)
		if (b[x][i]&&i!=pre)
			dfsb(i,x);
}
int vis[N];
void dfs(int x,int pre){
	vis[x]=1;
	For(i,1,n)
		if (a[x][i]&&b[x][i]&&i!=pre)
			dfs(i,x);
}
bool check(int x){
	if (vis[x]==2)
		return 1;
	if (vis[x]==1)
		return 0;
	vis[x]=1;
	for (auto y : e[x])
		if (!check(y))
			return 0;
	vis[x]=2;
	return 1;
}
int Solve(int x){
	clr(fa),clr(fb);
	dfsa(x,0);
	dfsb(x,0);
	clr(vis);
	dfs(x,0);
	For(i,1,n)
		e[i].clear();
	For(i,1,n){
		if (!vis[i]&&!vis[fa[i]])
			e[i].pb(fa[i]);
		if (!vis[i]&&!vis[fb[i]])
			e[fb[i]].pb(i);
	}
	int c=0;
	For(i,1,n)
		if (!vis[i])
			c++;
	clr(vis);
	For(i,1,n)
		if (!check(i))
			return INF;
	return c;
}
int ina[N],inb[N];
int SolveN(int x,int y){
	clr(fa),clr(fb);
	dfsa(x,0);
	dfsb(y,0);
	For(i,1,n)
		e[i].clear();
	For(i,1,n){
		if (i!=x&&i!=y&&fa[i]!=x&&fa[i]!=y)
			e[i].pb(fa[i]);
		if (i!=x&&i!=y&&fb[i]!=x&&fb[i]!=y)
			e[fb[i]].pb(i);
	}
	clr(vis);
	For(i,1,n)
		if (!check(i))
			return 0;
	return 1;
}
int SolveN(){
	clr(ina),clr(inb);
	For(i,1,n)
		For(j,1,n){
			if (a[i][j])
				ina[j]++;
			if (b[i][j])
				inb[j]++;
		}
	For(i,1,n)
		if (inb[i]==1)
			For(j,1,n)
				if (j!=i&&ina[j]==1)
					if (SolveN(i,j))
						return 1;
	return 0;
}
void Solve(){
	clr(a),clr(b);
	ans=INF;
	n=read();
	For(i,1,n-1){
		int x=read(),y=read();
		a[x][y]=a[y][x]=1;
	}
	For(i,1,n-1){
		int x=read(),y=read();
		b[x][y]=b[y][x]=1;
	}
	For(i,1,n)
		ans=min(ans,Solve(i));
	if (ans==INF)
		ans=SolveN()?n:-1;
	cout<<ans<<endl;
}
int main(){
	int T=read();
	while (T--)
		Solve();
	return 0;
}