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>
 
#pragma optimize("no-stack-protector")
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(a) a.begin(), a.end()
#define lowbit(x) ((x) & -(x))
 
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> VI;
 
namespace io {
	const int L = (1 << 21) + 1;
	char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, L, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
	inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	template <class I> inline void gi (I & x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I> inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0', x /= 10;
		while (qr) putc (qu[qr --]);
	}
	inline char read () {
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		return c;
	}
	inline void gs (char *s) {
		int l;
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		for (l = 0; c <= 'z' && c >= 'a'; c = gc()) s[l] = c, ++l;
		s[l] = 0;
	}
	inline void ps (const char *s) {
		int l = strlen(s), i;
		for (i = 0; i < l; i ++) putc(s[i]);
	}
	struct IOC { ~ IOC () { flush (); } } _ioc_;
	inline double readld(){
		double x = 0, y = 1;
		for (c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') y = -1;
		assert(c != '.');
		for (c = gc(); c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
		x *= y;
		assert(c != 'e');
		if (c == '.') for (c = gc(); c <= '9' && c >= '0'; c = gc()) y *= 0.1, x += y * (c & 15);
		return x;
	}
	inline void printld(double x, int digit){
		if (x < 0) putc('-'), x = -x;
		x += 0.5 * pow(0.1, digit);
		print((ll)x), putc('.');
		for (x -= (ll)x; digit; --digit) x = x * 10, putc((int)x + '0'), x -= (int)x;
	}
} ;
using io::gi;
using io::gs;
using io::ps;
using io::putc;
using io::read;
using io::print;
using io::readld;
using io::printld;
 
inline int ctz(int a){ return __builtin_ctz(a); }
inline int ctz(uint a){ return __builtin_ctz(a); }
inline int ctz(ll a){ return __builtin_ctzll(a); }
inline int ctz(ull a){ return __builtin_ctzll(a); }
template <class T> inline T gcd(T a, T b){
	int shift = ctz(a | b);
	for (b >>= ctz(b), a >>= ctz(a); a; a -= b, a >>= ctz(a)) if (a < b) swap(a, b);
	return b << shift;
}
template <class T> void exgcd(T a, T b, T &x, T &y){
	if (!b) return (void)(x = 1, y = 0);
	exgcd(b, a % b, y, x), y -= a / b * x;
}
template<class T> T inv(T a, T p){
	T x, y;
	exgcd(a, p, x, y);
	return (x % p + p) % p;
}
int fpow(int a, int t, int p){
	static int r;
	for (r = 1; t; a = (ll)a * a % p, t >>= 1) if (t & 1) r = (ll)r * a % p;
	return r;
}
 
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template<class A> string to_string(A v) {
	bool first = true; string res = "{";
	for (const auto &x : v) {
		if (!first) res += ", ";
		first = false, res += to_string(x);
	}
	res += "}";
	return res;
}
void debug_out() { cerr << endl; }
template<class A, class...B> void debug_out(A H, B... T) { cerr << " " << to_string(H), debug_out(T...); }
void scan(){}
template<class A, class...B> void scan(A &a, B &... b) { gi(a), scan(b...); }
 
template <class T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
template <class T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
 
const int N=55;
int T,n,fa[N],ans;
bool vis[N],in[N];
vector<int>ta[N],tb[N];
void dfs(int u){
	vis[u]=true;
	bitset<N>ff=0;
	for(int v:ta[u])ff[v]=1;
	for(int v:tb[u])if(v!=fa[u]&&ff[v]==1)fa[v]=u,dfs(v);
}
void dfs1(int u){for(int v:ta[u])if(v!=fa[u])fa[v]=u,dfs1(v);}
void dfs2(int u){for(int v:tb[u])if(v!=fa[u])fa[v]=u,dfs2(v);}
vector<int>go[N];bool gg;
void dfs3(int u){
	in[u]=vis[u]=true;
	for(int v:go[u]){
		if(!vis[v])dfs3(v);
		else if(in[v])gg=true;
	}
	in[u]=false;
}
int main(){
	for(scan(T);T;T--){
		int i,r,u,v,c;
		scan(n);
		for(i=1;i<n;i++)scan(u,v),ta[u].pb(v),ta[v].pb(u);
		for(i=1;i<n;i++)scan(u,v),tb[u].pb(v),tb[v].pb(u);
		ans=n+1;
		for(r=1;r<=n;r++){
			for(i=1;i<=n;i++)vis[i]=false,go[i].clear();
			fa[r]=0,dfs(r);
			c=0;
			for(i=1;i<=n;i++)if(!vis[i])++c;
			dfs1(r);for(i=1;i<=n;i++)if(!vis[i]&&!vis[fa[i]])go[i].pb(fa[i]);
			dfs2(r);for(i=1;i<=n;i++)if(!vis[i]&&!vis[fa[i]])go[fa[i]].pb(i);
			for(i=1;i<=n;i++)vis[i]=false;
			gg=false;
			for(i=1;i<=n;i++)if(!vis[i])dfs3(i);
			if(!gg)ans=min(ans,c);
		}
		if(ans>n){
			for(u=1;u<=n;u++)if(tb[u].size()==1){
				for(v=1;v<=n;v++)if(u!=v){
					for(r=1;r<=n;r++)if(r!=u){
						for(i=1;i<=n;i++)go[i].clear();
						fa[u]=0;dfs1(u);for(i=1;i<=n;i++)if(fa[i])go[i].pb(fa[i]);
						fa[r]=0;dfs2(r);for(i=1;i<=n;i++)if(fa[i])go[fa[i]].pb(i);
						for(i=1;i<=n;i++)vis[i]=false;
						gg=false;
						for(i=1;i<=n;i++)if(!vis[i])dfs3(i);
						if(!gg){ans=n;break;}
					}
					if(ans==n)break;
				}
				if(ans==n)break;
			}
		}
		for(i=1;i<=n;i++)ta[i].clear(),tb[i].clear();
		if(ans>n)ans=-1;
		print(ans),putc('\n');
	}
}
/*
1
5
1 2
2 3
3 4
4 5
3 1
1 2
2 4
4 5
*/