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 ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=55,INF=1e9;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
vector<int>G1[MAXN],G2[MAXN],G3[MAXN],G4[MAXN];queue<int>q;
int n,d1[MAXN],d2[MAXN],p1[MAXN],p2[MAXN],deg[MAXN];
void dfs1(int x){for(int i=0,len=G2[x].size(),y;i<len;i++)if((y=G2[x][i])!=p1[x])p1[y]=x,dfs1(y);}
void dfs2(int x){for(int i=0,len=G3[x].size(),y;i<len;i++)if((y=G3[x][i])!=p2[x])p2[y]=x,dfs2(y);}
inline int Solve(int n,int rt){
	p1[rt]=p2[rt]=0,dfs1(rt),dfs2(rt);int s=0;
	Rep(i,1,n)G4[i].clear();memset(deg,0,sizeof(deg));
	Rep(i,1,n)if(p1[i]==p2[i]&&p1[p1[i]]!=p2[p1[i]])return INF;
	Rep(i,1,n)if(p1[i]!=p2[i]){
		s++;
		for(int j=0,len=G2[i].size(),y;j<len;j++)if((y=G2[i][j])!=p1[i])G4[y].push_back(i),deg[i]++;
		for(int j=0,len=G3[i].size(),y;j<len;j++)if((y=G3[i][j])!=p2[i])G4[i].push_back(y),deg[y]++;
	}Rep(i,1,n)if(!deg[i])q.push(i);
	for(int x;!q.empty();q.pop()){
		x=q.front();
		for(int i=0,len=G4[x].size(),y;i<len;i++)(!--deg[y=G4[x][i]])?q.push(y),0:0;
	}Rep(i,1,n)if(deg[i])return INF;return s;
}
int main(){
	for(int t=read();t--;){
		memset(d1,0,sizeof(d1)),memset(d2,0,sizeof(d2)),n=read();
		Rep(i,1,n)G1[i].clear(),G2[i].clear();
		Rep(i,1,n-1){int x=read(),y=read();G2[x].push_back(y),G2[y].push_back(x),d1[x]++,d1[y]++;}
		Rep(i,1,n-1){int x=read(),y=read();G1[x].push_back(y),G1[y].push_back(x),d2[x]++,d2[y]++;}
		Rep(i,1,n)G3[i]=G1[i];int ans=INF;Rep(i,1,n)ans=min(ans,Solve(n,i));
		if(ans==INF){
			Rep(i,1,n)if(d2[i]==1)Rep(j,1,n)if(j!=i){
				Rep(k,1,n)if(k!=i){G3[k].clear();for(int l=0,len=G1[k].size(),y;l<len;l++)if((y=G1[k][l])!=i)G3[k].push_back(y);}
				G3[j].push_back(i),G3[i].clear(),G3[i].push_back(j),ans=min(ans,Solve(n,i)+1);
			}
		}if(ans<INF)cout<<ans<<'\n';else puts("-1");
	}
	return 0;
}