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 meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
auto rd=read<int>;
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;

std::vector<int> ta[51], tb[51];
int n, pa[51], pb[51];
void dfsa(int u, int p) {
	pa[u]=p;
	for(int v: ta[u]) if(v!=p) dfsa(v, u);
}
void dfsb(int u, int p) {
	pb[u]=p;
	for(int v: tb[u]) if(v!=p) dfsb(v, u);
}
u32 solve(int root, u32 res) {
	std::queue<int> q;
	std::vector<int> e[51];
	int ideg[51]={};
	dfsa(root, 0);
	dfsb(root, 0);
	for(int i=1; i<=n; ++i) if(pa[i]==pb[i]&&pa[pa[i]]!=pb[pa[i]]) return -1;
	for(int i=1; i<=n; ++i)
		if(pa[i]!=pb[i]) {
			if(pa[pa[i]]!=pb[pa[i]]) e[i].push_back(pa[i]), ++ideg[pa[i]];
			if(pa[pb[i]]!=pb[pb[i]]) e[pb[i]].push_back(i), ++ideg[i];
		}
	for(int i=1; i<=n; ++i) if(ideg[i]==0) q.push(i);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int v: e[u]) if(--ideg[v]==0) q.push(v);
	}
	for(int i=1; i<=n; ++i) if(ideg[i]!=0) return -1;
	for(int i=1; i<=n; ++i) res+=pa[i]!=pb[i];
	return res;
}
void work() {
	u32 ans=-1;
	n=rd();
	for(int i=1; i<=n; ++i) {
		ta[i].clear();
		tb[i].clear();
	}
	for(int i=1; i<n; ++i) {
		int u=rd(), v=rd();
		ta[u].push_back(v);
		ta[v].push_back(u);
	}
	for(int i=1; i<n; ++i) {
		int u=rd(), v=rd();
		tb[u].push_back(v);
		tb[v].push_back(u);
	}
	for(int i=1; i<=n; ++i) cmin(ans, solve(i, 0));
	for(int i=1; i<=n&&ans==-1; ++i)
		if(ta[i].size()==1) {
			int j=ta[i][0];
			std::remove(ta[j].begin(), ta[j].end(), i);
			ta[j].pop_back();
			for(int k=1; k<=n&&ans==-1; ++k)
				if(k!=i&&k!=j) {
					ta[i][0]=k;
					ta[k].push_back(i);
					ta[k].pop_back();
					cmin(ans, solve(i, 1));
				}
			ta[i][0]=j;
			ta[j].push_back(i);
		}
	printf("%d\n", ans);
}
int main() {
	int t=rd();
	while(t--) work();
	return 0;
}