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;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=55;
bool mark[N];
bool g[N][N];
VI e1[N],e2[N],e[N];
int q[N],deg[N],skip,n,u,v,ans,_;
void dfs1(int u,int f) {
	mark[u]=1;
	skip++;
	for (auto v:e1[u]) if (v!=f) {
		if (g[u][v]) {
			dfs1(v,u);
		}
	}
}
void dfs2(int u,int f) {
	for (auto v:e1[u]) if (v!=f) {
		dfs2(v,u);
		if (!mark[u]) e[v].pb(u);
	}
}
void dfs3(int u,int f) {
	for (auto v:e2[u]) if (v!=f) {
		dfs3(v,u);
		if (!mark[u]) e[u].pb(v);
	}
}
bool check() {
//	puts("chk");
	rep(u,1,n+1) for (auto v:e[u]) {
		deg[v]++;
//		printf("%d %d\n",u,v);
	}
	int t=0;
	rep(u,1,n+1) if (deg[u]==0) q[t++]=u;
	rep(i,0,t) {
		int u=q[i];
		for (auto v:e[u]) {
			--deg[v];
			if (deg[v]==0) q[t++]=v;
		}
	}
	return t==n;
}
void solve() {
	scanf("%d",&n);
	rep(i,1,n+1) {
		e1[i].clear(),e2[i].clear();
		rep(j,1,n+1) g[i][j]=0;
	}
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e1[u].pb(v); e1[v].pb(u);
	}
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e2[u].pb(v); e2[v].pb(u);
		g[u][v]=g[v][u]=1;
	}
	ans=n+1;
	rep(i,1,n+1) {
		rep(j,1,n+1) mark[j]=0;
		skip=0;
		dfs1(i,0);
		rep(j,1,n+1) e[j].clear(),deg[j]=0;
		dfs2(i,0);
		dfs3(i,0);
		if (check()) ans=min(ans,n-skip);
	}
	rep(i,1,n+1) if (SZ(e1[i])==1) rep(i2,1,n+1) {
		rep(j,1,n+1) e[j].clear(),deg[j]=0,mark[j]=0;
		dfs2(i2,0);
		dfs3(i,0);
		if (check()) {
			ans=min(ans,n);
		}
	}
	if (ans==n+1) ans=-1;
	printf("%d\n",ans);
}
int main() {
	for (scanf("%d",&_);_;_--) {
		solve();
	}
}