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>
using namespace std;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=2509;
	int n;
	queue<int> q;
	struct tree{
		int fa[N],deg[N],head[N],nex[N<<1],to[N<<1],cnt;
		inline void add(int u,int v){
			nex[++cnt]=head[u];
			head[u]=cnt,to[cnt]=v,deg[v]++;
		}
		inline void getfa(int u,int _f){
			fa[u]=_f;
			for(int i=head[u];i;i=nex[i])
				if(to[i]^_f) getfa(to[i],u);
		}
		inline bool topsort(){
			while(!q.empty()) q.pop();
			for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
			int tot=0;
			while(!q.empty()){
				int u=q.front();q.pop();
				tot++;
				for(int i=head[u];i;i=nex[i])
					if(!--deg[to[i]]) q.push(to[i]);
			}
			return tot==n;
		}
	}A,B,G;
	inline int solve(){
		for(int i=1;i<=n;i++)
			if(A.fa[i]==B.fa[i] && A.fa[A.fa[i]]!=B.fa[A.fa[i]]) return n+1;
		for(int i=1;i<=n;i++) G.head[i]=G.deg[i]=0;G.cnt=0;
		int ret=0;
		for(int i=1;i<=n;i++){
			if(A.fa[i]!=B.fa[i]) G.add(i,A.fa[i]),ret++;
			if(A.fa[B.fa[i]]!=B.fa[B.fa[i]]) G.add(B.fa[i],i);
		}
		if(G.topsort()) return ret;
		else return n+1;
	}
	int main(){
		int T=read<int>();
		while(T--){
			n=read<int>();
			A.cnt=B.cnt=0;
			for(int i=1;i<=n;i++) A.head[i]=B.head[i]=A.deg[i]=B.deg[i]=0;
			for(int i=1;i<n;i++){
				int u=read<int>(),v=read<int>();
				A.add(u,v),A.add(v,u);
			}
			for(int i=1;i<n;i++){
				int u=read<int>(),v=read<int>();
				B.add(u,v),B.add(v,u);
			}
			int ans=n+1;
			for(int i=1;i<=n;i++){
				A.getfa(i,0),B.getfa(i,0),ans=min(ans,solve());
				if(A.deg[i]==1)
					for(int j=1;j<=n;j++) if(j^i){
						A.getfa(j,0),A.fa[j]=i,A.fa[i]=0;
						ans=min(ans,solve()+1);
					}
			}
			if(ans<=n) printf("%d\n",ans);
			else puts("-1");
		}
		return 0;
	}
}
int main(){
#ifdef my
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	return run::main();
}