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<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
void read(bool A[51][51]) {
    REP (i, N) REP (j, N) A[i][j] = false;
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	A[x][y] = 1;
	A[y][x] = 1;
    }
}
bool A[51][51];
bool B[51][51];
bool W[51][51];
bool use[51];


void MAIN() {
    scanf("%d", &N);
    read(A);
    read(B);

    bool same = true;
    REP (i, N) REP (j, N) if (A[i][j] != B[i][j]) {
	same = false;
    }

    int ans = -1;
    if (same) {
	ans = 0;
    } else {
	VI ord;

	REP (s, N) if (count(A[s], A[s]+N, true) == 1) {
	    REP (t, N) if (s != t) {
		memset(use, 0, sizeof use);
		REP (i, N) REP (j, N) W[i][j] = A[i][j];

		REP (i, N) W[i][s] = W[s][i] = false;
		W[s][t] = W[t][s] = true;
		use[s] = true;
		ord.clear();
		ord.push_back(s);

		for (int i=0; i<(int)ord.size(); i++) {
		    int v = ord[i];
		    REP (j, N) if (!use[j] && B[v][j] && W[v][j]) {
			use[j] = true;
			ord.push_back(j);
		    }
		}

		while (1) {
		    bool update = false;
		    REP (j, N) if (!use[j] && count(W[j], W[j]+N, true) == 1) {
			REP (k, N) if (use[k] && B[j][k]) {
			    use[j] = true;
			    REP (l, N) W[j][l] = W[l][j] = false;
			    W[j][k] = W[k][j] = true;
			    update = true;
			}
		    }
		    if (!update) break;
		}

		if (count(use, use+N, true) == N) {
		    int tmp = N+1 - (int)ord.size();
		    if (ans == -1 || ans > tmp) ans = tmp;
		}
	    }
	}
    }

    printf("%d\n", ans);
}

int main() {
    int TC = 1;
    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}