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 rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
 
template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=55;
int a[N],b[N],c[N],d[N],deg[N],nei[N],mark[N];
ll preT[N],preE[N];
vi t[N],e[N];
int n,ans,cnt;

void T(int u,int fa,ll s){
	preT[u]=s,s|=1ll<<u;
	for(auto v:t[u])
		if(v!=fa)T(v,u,s);
}

void E(int u,int fa,ll s){
	preE[u]=s,s|=1ll<<u;
	for(auto v:e[u])
		if(v!=fa)E(v,u,s);
}

void dfs(int u,int fa){
	cnt++;
	sort(t[u].begin(),t[u].end());
	sort(e[u].begin(),e[u].end());
	for(int i=0,j=0;i<t[u].size()||j<e[u].size();i++,j++){
		int a=(i<t[u].size()?t[u][i]:n+1);
		int b=(j<e[u].size()?e[u][j]:n+1);
		if(a==fa&&b==fa)continue;
		if(a==b)dfs(a,u);
		else if(a<b)T(a,u,0),j--;
		else E(b,u,0),i--;
	}
}

void doit(int x,int y){		// first step: x -> y
	rep(i,1,n){
		t[i].clear(),e[i].clear();
		mark[i]=preT[i]=preE[i]=0;
	}
	t[x].pb(y),t[y].pb(x);
	rep(i,1,n-1){
		if(a[i]!=x&&b[i]!=x)
			t[a[i]].pb(b[i]),t[b[i]].pb(a[i]);
		e[c[i]].pb(d[i]),e[d[i]].pb(c[i]);
	}
	cnt=-1,dfs(x,0);
	rep(i,1,n)rep(j,1,n)
		if(preT[i]>>j&1)preE[j]|=1ll<<i;
	rep(i,1,n)rep(j,1,n)
		if(preE[j]>>i&1)preE[j]|=preE[i];
	rep(i,1,n)if(preE[i]>>i&1)return;
	ans=min(ans,n-cnt);
}

void rmain(){
	map<pii,int> owo; int same=1;
	read(n),fill(deg+1,deg+n+1,0),ans=n+1;
	rep(i,1,n-1){
		read(a[i]),read(b[i]);
		if(a[i]>b[i])swap(a[i],b[i]);
		owo[mp(a[i],b[i])]=1;
		deg[a[i]]++,deg[b[i]]++;
		nei[a[i]]=b[i],nei[b[i]]=a[i];
	}
	rep(i,1,n-1){
		read(c[i]),read(d[i]);
		if(c[i]>d[i])swap(c[i],d[i]);
		if(!owo[mp(c[i],d[i])])same=0;
	}
	if(same){puts("0");return;}
	rep(i,1,n)if(deg[i]==1)
		rep(j,1,n)if(i!=j&&i!=nei[i])
			doit(i,j);
	printf("%d\n",ans<=n?ans:-1);
}

int main(){
	int T; read(T);
	while(T--) rmain();	
	return 0;
}