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 mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int N=60;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
int n,ans=inf,fa1[N],fa2[N],vis[N],cnt=0,du[N];
vector<int> E1[N],E2[N],E[N];
void dfs1(int u,int fa) {
    fa1[u]=fa;
    for(int v:E1[u]) if(v!=fa) dfs1(v,u);
}
void dfs2(int u,int fa) {
    fa2[u]=fa;
    if(!fa) vis[u]=1,++cnt;
    else {
        vis[u]=vis[fa]&&(fa1[u]==fa2[u]);
        if(vis[u]) ++cnt;
    }
    for(int v:E2[u]) if(v!=fa) dfs2(v,u);
}
void solve(int u) {
    cnt=0,clr(du),clr(vis);
    for(int i=1;i<=n;i++) E[i].clear();
    dfs1(u,0),dfs2(u,0);
    for(int i=1;i<=n;i++)
        if(i!=u) {
            if(!vis[i]&&!vis[fa1[i]]) E[i].pb(fa1[i]),++du[fa1[i]];
            if(!vis[i]&&!vis[fa2[i]]) E[fa2[i]].pb(i),++du[i];
        }
    queue<int> q;
    for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int v:E[u]) if(!--du[v]) q.push(v);
    }
    for(int i=1;i<=n;i++) if(du[i]) return;
    chkmin(ans,n-cnt);
}
void work() {
    n=gi(),ans=inf;
    for(int i=1;i<=n;i++) E1[i].clear(),E2[i].clear();
    for(int i=1,u,v;i<n;i++) u=gi(),v=gi(),E1[u].pb(v),E1[v].pb(u);
    for(int i=1,u,v;i<n;i++) u=gi(),v=gi(),E2[u].pb(v),E2[v].pb(u);
    int fl=1;
    for(int i=1;i<=n;i++) {
        sort(all(E1[i])),sort(all(E2[i]));
        if(E1[i]!=E2[i]) fl=0;
    }
    if(fl) { puts("0");return; }
    for(int i=1;i<=n;i++)
        if(sz(E1[i])==1) {
            int j=E1[i][0];
            for(int &x:E1[j]) if(x==i) { swap(x,E1[j].back());break; }
            for(int k=1;k<=n;k++)
                if(k!=i) {
                    E1[i].pop_back(),E1[j].pop_back(),E1[k].pb(i),E1[i].pb(k);
                    solve(i);
                    E1[k].pop_back(),E1[i].pop_back(),E1[i].pb(j),E1[j].pb(i);
                }
        }
    if(ans==inf) puts("-1");
    else printf("%d\n",ans+1);
}
int main() {
    int T=gi();
    while(T--) work();
    return 0;
}