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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<bitset>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

typedef bitset<51> B;

struct UF{
	int par[100];
	void init(){
		rep(i,100)par[i] = i;
	}
	int find(int x){
		if(par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
	void unit(int x,int y){
		if(same(x,y))return;
		x = find(x);
		y = find(y);
		par[x] = y;
	}
}uf;

int N;
struct Tree{
	int d[52];
	vector<int> G[52];
	void clear(){
		rep(i,52){
			G[i].clear();
			d[i] = 0;
		}
	}
}X,Y;

bool f(Tree X_,B b){
	int cnt = b.count();
	set<int> S;
	for(int i = 1 ; i <= N ; i ++){
		if(X_.d[i] == 1 && !b[i])S.insert(i);
	}
	while(cnt < N){
		bool update = false;
		for(int i = 1 ; i <= N ; i ++){
			if(b[i])continue;
			bool s = false;
			for(int j: Y.G[i]){
				if(b[j]){
					s = true;
					break;
				}
			}
			if(!s)continue;
			if(S.find(i) != S.end()){
				S.erase(i);
				for(int j: X_.G[i]){
					X_.d[j] --;
					if(X_.d[j] == 1 && !b[j])S.insert(j);
				}
				b[i] = true;
				update = true;
				cnt ++;
			}
		}
		if(!update)return false;
	}
	return true;
}

bool g(Tree X_, int v){
	for(int u: X_.G[v]){
		X_.d[u] --;
	}
	B b;
	b[v] = true;
	return f(X_,b);
}

int main(){
	int T;
	scanf("%d",&T);
	rep(ppp,T){
		uf.init();
		int a[50],b[50],c[50],d[50];
		scanf("%d",&N);
		for(int i = 0 ; i < N-1 ; i ++){
			scanf("%d%d",&a[i],&b[i]);
			if(a[i]>b[i])swap(a[i],b[i]);
		}
		for(int i = 0 ; i < N-1 ; i ++){
			scanf("%d%d",&c[i],&d[i]);
			if(c[i]>d[i])swap(c[i],d[i]);
		}
		set<P> S;
		rep(i,N-1)S.insert(P(a[i],b[i]));
		rep(i,N-1){
			if(S.find(P(c[i],d[i])) != S.end()){
				uf.unit(c[i],d[i]);
			}
		}
		
		X.clear();
		Y.clear();
		for(int i = 0 ; i <N-1 ; i ++){
			X.G[a[i]].push_back(b[i]);
			X.G[b[i]].push_back(a[i]);
			X.d[a[i]] ++;
			X.d[b[i]] ++;
		}
		for(int i = 0 ; i <N-1 ; i ++){
			Y.G[c[i]].push_back(d[i]);
			Y.G[d[i]].push_back(c[i]);
			Y.d[c[i]] ++;
			Y.d[d[i]] ++;
		}
		
		int ret = 10000;
		for(int i = 1 ; i <= N ; i ++){
			if(uf.find(i) != i)continue;
			B b;
			for(int j = 1 ; j <= N ; j ++){
				if(uf.find(j) == i)b[j] = true;
			}
			int t = b.count();
			//cout << b << endl;
			if(f(X,b))ret = min( ret , N-t );
		}
		for(int i = 1 ; i <= N ; i ++){
			if(X.d[i] == 1){
				if(g(X,i))ret = min( ret , N );
			}
		}
		if(ret == 10000)cout << -1 << endl;
		else cout << ret << endl;
	}
}