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<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=2147483646;
int fb;
struct tree{
	int h[60],nex[110],to[110],M;
	void reset(){
		M=0;
		memset(h,0,sizeof(h));
	}
	void add(int a,int b){
		M++;
		to[M]=b;
		nex[M]=h[a];
		h[a]=M;
	}
	int fa[60];
	void dfs(int x){
		for(int i=h[x];i;i=nex[i]){
			if(to[i]!=fa[x]&&to[i]!=fb){
				fa[to[i]]=x;
				dfs(to[i]);
			}
		}
	}
}a,b;
int d[60],v[60],n,M;
bool f[60];
void dfs(int fa,int x){
	int i,tm;
	tm=++M;
	f[x]=1;
	for(i=a.h[x];i;i=a.nex[i])v[a.to[i]]=tm;
	for(i=b.h[x];i;i=b.nex[i]){
		if(b.to[i]!=fa&&v[b.to[i]]==tm&&b.to[i]!=fb)dfs(x,b.to[i]);
	}
}
struct graph{
	int h[60],nex[110],to[110],M;
	bool v[60],ins[60];
	void reset(){
		M=0;
		memset(h,0,sizeof(h));
		memset(v,0,sizeof(v));
		memset(ins,0,sizeof(ins));
	}
	void add(int a,int b){
		M++;
		to[M]=b;
		nex[M]=h[a];
		h[a]=M;
	}
	bool dfs(int x){
		v[x]=1;
		ins[x]=1;
		for(int i=h[x];i;i=nex[i]){
			if(!v[to[i]]){
				if(!dfs(to[i]))return 0;
			}else if(ins[to[i]])
				return 0;
		}
		ins[x]=0;
		return 1;
	}
}g;
int solve(int r){
	fb=r;
	int i,cnt;
	memset(a.fa,0,sizeof(a.fa));
	a.dfs(r);
	memset(b.fa,0,sizeof(b.fa));
	b.dfs(r);
	memset(f,0,sizeof(f));
	dfs(0,r);
	g.reset();
	cnt=0;
	for(i=1;i<=n;i++){
		if(!f[i]){
			if(!f[a.fa[i]])g.add(i,a.fa[i]);
			if(!f[b.fa[i]])g.add(b.fa[i],i);
			cnt++;
		}
	}
	for(i=1;i<=n;i++){
		if(!g.dfs(i))return inf;
	}
	return cnt;
}
void work(){
	int i,j,x,y,ans;
	scanf("%d",&n);
	a.reset();
	b.reset();
	memset(d,0,sizeof(d));
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		a.add(x,y);
		a.add(y,x);
		d[x]++;
		d[y]++;
	}
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		b.add(x,y);
		b.add(y,x);
	}
	ans=inf;
	for(i=1;i<=n;i++)ans=min(ans,solve(i));
	for(i=1;i<=n;i++){
		if(d[i]==1){
			for(j=1;j<=n;j++){
				if(j!=i){
					x=a.to[a.h[i]];
					a.to[a.h[i]]=j;
					ans=min(ans,solve(i)+1);
					a.to[a.h[i]]=x;
				}
			}
		}
	}
	if(ans==inf)ans=-1;
	printf("%d\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}