Given two trees $S$ and $T$ each containing $n$ nodes, where nodes are numbered from $1$ to $n$ and the root of both trees is node $1$. Calculate the number of pairs $(x, y)$ such that $x < y$ and $\text{LCA}_S(x, y) = \text{LCA}_T(x, y)$.

$\text{LCA}_S(x, y)$ denotes the lowest common ancestor of nodes $x$ and $y$ in tree $S$, which is the node $z$ furthest from the root that is an ancestor of both $x$ and $y$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 2 \times 10^4$). The format for each test case is as follows:

The first line contains an integer $n$ ($2 \le n \le 2 \times 10^5$), representing the number of nodes in the trees.

The next $n - 1$ lines each contain two integers $u_{S,i}$ and $v_{S,i}$ ($1 \le u_{S,i}, v_{S,i} \le n$), representing an edge in tree $S$.

The next $n - 1$ lines each contain two integers $u_{T,i}$ and $v_{T,i}$ ($1 \le u_{T,i}, v_{T,i} \le n$), representing an edge in tree $T$.

Within each test file, it is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output a single integer on a new line representing the number of pairs satisfying the condition.

Examples

Input 1

4
2
1 2
2 1
3
1 2
1 3
1 2
2 3
3
1 3
2 3
1 2
1 3
7
1 2
1 3
2 4
2 5
3 6
3 7
1 2
1 4
2 5
2 3
4 6
4 7

Output 1

1
2
2
12