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:
#ifdef xay5420
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#define NDEBUG
#endif
#include<bits/stdc++.h>
#define pop64 __builtin_popcountll
#define ctz64 __builtin_ctzll
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long LL;
const int N=55;
int T,n,f1[N],f2[N];
LL G1[N],G2[N];
void dfs1(int k1,int k2){
	f1[k1]=k2;
	for(LL i=G1[k1];i;i&=i-1){
		int j=ctz64(i);
		if(j!=k2){
			dfs1(j,k1);
		}
	}
}
void dfs2(int k1,int k2){
	f2[k1]=k2;
	for(LL i=G2[k1];i;i&=i-1){
		int j=ctz64(i);
		if(j!=k2){
			dfs2(j,k1);
		}
	}
}
LL H[N];
int deg[N];
int sol(int rt){
	/*rep(i,1,n)D("%d ",G1[i]);
	D("\n");*/
	dfs1(rt,0),dfs2(rt,0);
	rep(i,1,n)if(f1[i]==f2[i])if(f1[f1[i]]!=f2[f2[i]])return n+1;
	auto chk=[&](int k1){
		return f1[k1]!=f2[k1];
	};
	rep(i,1,n)H[i]=deg[i]=0;
	int tot=0;
	rep(i,1,n)if(chk(i)){
		if(chk(f1[i])){
			H[i]|=1LL<<f1[i],++deg[f1[i]];
		}
		++tot;
	}
	rep(i,1,n)if(chk(i)){
		if(chk(f2[i])){
			if(~H[f2[i]]>>i&1){
				H[f2[i]]|=1LL<<i,++deg[i];
			}
		}
	}
	static int q[N];
	int he=0,ta=0;
	rep(i,1,n)if(chk(i)&&!deg[i])q[++ta]=i;
	while(he!=ta){
		int k1=q[++he];
		for(LL i=H[k1];i;i&=i-1){
			int j=ctz64(i);
			if(!--deg[j]){
				q[++ta]=j;
			}
		}
	}
	if(ta==tot)return tot+1;
	else return D("bad\n"),n+1;
}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	scanf("%d",&T);
	rep(_,1,T){
		//D("now %d\n",_);
		scanf("%d",&n);
		int ans=n+1;
		memset(G1,0,sizeof(G1));
		memset(G2,0,sizeof(G2));
		rep(i,2,n){
			int k1,k2;scanf("%d%d",&k1,&k2);
			G1[k1]|=1LL<<k2;
			G1[k2]|=1LL<<k1;
		}
		rep(i,2,n){
			int k1,k2;scanf("%d%d",&k1,&k2);
			G2[k1]|=1LL<<k2;
			G2[k2]|=1LL<<k1;
		}
		if(!memcmp(G1+1,G2+1,sizeof(G1[0])*n)){
			puts("0");
			continue;
		}
		rep(k1,1,n)if((G1[k1]&(G1[k1]-1))==0){
			int k2=ctz64(G1[k1]);
			G1[k1]=0,G1[k2]^=1LL<<k1;
			rep(i,1,n)if(i!=k1&&i!=k2){
				G1[k1]=1LL<<i;
				G1[i]^=1LL<<k1;
				//D(">>> %d %d %d\n",k1,i,sol(k1));
				ans=min(ans,sol(k1));
				G1[k1]=0;
				G1[i]^=1LL<<k1;
			}
			G1[k1]^=1LL<<k2,G1[k2]^=1LL<<k1;
		}
		printf("%d\n",ans>n?-1:ans);
	}
	return 0;
}