Dane są dwie drzewa $S$ oraz $T$, każde o $n$ wierzchołkach. Wierzchołki w obu drzewach są ponumerowane od $1$ do $n$, a korzeniem każdego z nich jest wierzchołek $1$. Oblicz, ile istnieje par $(x, y)$ takich, że $x < y$ oraz $\text{LCA}_S(x, y) = \text{LCA}_T(x, y)$.

$\text{LCA}_S(x, y)$ oznacza najniższego wspólnego przodka wierzchołków $x$ oraz $y$ w drzewie $S$, czyli wierzchołek $z$ położony najdalej od korzenia, który jest przodkiem zarówno $x$, jak i $y$.

Wejście

Każdy plik testowy zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 2 \times 10^4$). Format każdego zestawu danych jest następujący:

Pierwsza linia zawiera liczbę całkowitą $n$ ($2 \le n \le 2 \times 10^5$), oznaczającą liczbę wierzchołków w drzewach.

Następne $n - 1$ linii zawiera po dwie liczby całkowite $u_{S,i}$ oraz $v_{S,i}$ ($1 \le u_{S,i}, v_{S,i} \le n$), opisujące krawędzie drzewa $S$.

Następne $n - 1$ linii zawiera po dwie liczby całkowite $u_{T,i}$ oraz $v_{T,i}$ ($1 \le u_{T,i}, v_{T,i} \le n$), opisujące krawędzie drzewa $T$.

Suma $n$ dla wszystkich zestawów danych w jednym pliku testowym nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą oznaczającą liczbę par spełniających podany warunek.

Przykład

Wejście 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

Wyjście 1

1
2
2
12