Problem Statement

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.