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:
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c<=32)c=_buff.get();return c;}
ll qpow(ll x,ll k){return k==0?1:1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int Tn,n;
bool adj[55][55];
bool nadj[55][55];
bool vis[55],ty[55];
int fa[55];
void dfs(int x,bool flag)
{
	vis[x]=1;ty[x]=flag;
	for(int i=1;i<=n;i++)
	{
		if(adj[x][i]&&!vis[i])
		{
			fa[i]=x;
			dfs(i,flag&nadj[x][i]);
		}
	}
}
int mk[55],deg[55];
int q[233],qn;
void mark(int x,int c)
{
	mk[x]=c;
	for(int i=1;i<=n;i++)
	{
		if(nadj[x][i]&&mk[x]==2&&mk[i]==1)
		{
			q[qn++]=i;
			q[qn++]=x;
		}
		if(nadj[x][i]&&mk[x]==1&&mk[i]==2)
		{
			q[qn++]=x;
			q[qn++]=i;
		}
	}
}
int solve(int S)
{
	memset(vis,0,sizeof(vis));
	fa[S]=0;
	dfs(S,1);
	for(int i=1;i<=n;i++)if(!vis[i])return n+1;
	qn=0;
	memset(mk,0,sizeof(mk));
	memset(deg,0,sizeof(deg));
	for(int i=1;i<=n;i++)deg[fa[i]]++;
	for(int i=1;i<=n;i++)
	{
		if(ty[i])mark(i,2);
		else if(deg[i]==0)mark(i,1);
	}
	int cnt=0;
	for(int i=0;i<qn;i+=2)
	{
		int x=q[i],y=q[i+1];
		if(mk[x]==1)
		{
			cnt++;
			mark(x,2);
			deg[fa[x]]--;
			if(deg[fa[x]]==0&&mk[fa[x]]==0)mark(fa[x],1);
		}
	}
	for(int i=1;i<=n;i++)if(mk[i]!=2)return n+1;
	return cnt;
}
void solve()
{
	memset(adj,0,sizeof(adj));
	memset(nadj,0,sizeof(nadj));
	geti(n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		getii(x,y);
		adj[x][y]=adj[y][x]=1;
	}
	bool same=1;
	for(int i=1;i<n;i++)
	{
		int x,y;
		getii(x,y);
		same&=adj[x][y];
		nadj[x][y]=nadj[y][x]=1;
	}
	if(same)
	{
		puts("0");
		return;
	}
	int ans=n+1;
	for(int i=1;i<=n;i++)
	{
		int d=0;
		for(int j=1;j<=n;j++)d+=adj[i][j];
		if(d!=1)continue;
		for(int j=1;j<=n;j++)
		{
			if(!adj[i][j])continue;
			for(int k=1;k<=n;k++)
			{
				if(adj[i][k])continue;
				adj[i][j]=0;
				adj[i][k]=1;
				ans=min(ans,solve(i)+1);
				adj[i][j]=1;
				adj[i][k]=0;
			}
		}
	}
	if(ans>n)puts("-1");
	else cout<<ans<<endl;
}
int main()
{
	geti(Tn);
	while(Tn--)
	{
		solve();
	}
	return 0;
}