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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <cmath>
#include <string>
#include <set>
#include <map>
#define SIZE 55

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

vector <int> A[SIZE];
vector <int> B[SIZE];
int pa[SIZE],pb[SIZE];
int deg[SIZE];
bool use[SIZE];

void dfs_a(int v,int p)
{
	pa[v]=p;
	for(int i=0;i<A[v].size();i++)
	{
		int to=A[v][i];
		if(to!=p) dfs_a(to,v);
	}
}
void dfs_b(int v,int p)
{
	pb[v]=p;
	for(int i=0;i<B[v].size();i++)
	{
		int to=B[v][i];
		if(to!=p) dfs_b(to,v);
	}
}
void solve()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) A[i].clear();
	for(int i=0;i<n;i++) B[i].clear();
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--,b--;
		A[a].push_back(b);
		A[b].push_back(a);
	}
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--,b--;
		B[a].push_back(b);
		B[b].push_back(a);
	}
	dfs_a(0,-1);
	dfs_b(0,-1);
	bool up=true;
	for(int i=0;i<n;i++) if(pa[i]!=pb[i]) up=false;
	if(up)
	{
		puts("0");
		return;
	}
	int ans=-1;
	for(int s=0;s<n;s++)
	{
		if(A[s].size()==1)
		{
			int t=A[s][0];
			for(int i=0;i<A[t].size();i++)
			{
				if(A[t][i]==s)
				{
					swap(A[t][i],A[t][A[t].size()-1]);
					break;
				}
			}
			A[t].pop_back();
			for(int i=0;i<n;i++)
			{
				// s->i に辺を張る
				A[s][0]=i;
				A[i].push_back(s);
				dfs_a(s,-1);
				dfs_b(s,-1);
				memset(use,false,sizeof(use));
				queue <int> que;
				int cnt=0;
				que.push(s);
				while(!que.empty())
				{
					int v=que.front();que.pop();
					use[v]=true;
					cnt++;
					for(int j=0;j<A[v].size();j++)
					{
						int to=A[v][j];
						if(to!=pa[v]&&pb[to]==v) que.push(to);
					}
				}
				for(int j=0;j<n;j++)
				{
					deg[j]=A[j].size()-1;
				}
				while(1)
				{
					int v=-1;
					for(int j=0;j<n;j++)
					{
						if(!use[j]&&deg[j]==0&&use[pb[j]])
						{
							v=j;
							break;
						}
					}
					if(v==-1) break;
					use[v]=true;
					deg[pa[v]]--;
				}
				bool up=true;
				for(int j=0;j<n;j++)
				{
					if(!use[j])
					{
						up=false;
					}
				}
				if(up)
				{
					int vl=n-cnt+1;
					if(ans==-1) ans=vl;
					else ans=min(ans,vl);
				}
				A[i].pop_back();
			}
			A[t].push_back(s);
			A[s][0]=t;
		}
	}
	printf("%d\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}