Даны два дерева $S$ и $T$, каждое из которых содержит $n$ вершин. Вершины пронумерованы от $1$ до $n$, корень каждого дерева находится в вершине $1$. Вычислите количество пар $(x, y)$, таких что $x < y$ и $\text{LCA}_S(x, y) = \text{LCA}_T(x, y)$.

$\text{LCA}_S(x, y)$ обозначает наименьшего общего предка вершин $x$ и $y$ в дереве $S$, то есть вершину $z$, наиболее удаленную от корня, которая является предком как $x$, так и $y$.

Входные данные

Каждый файл теста содержит несколько наборов входных данных. Первая строка содержит количество наборов данных $T$ ($1 \le T \le 2 \times 10^4$). Формат каждого набора данных следующий:

Первая строка содержит целое число $n$ ($2 \le n \le 2 \times 10^5$), количество вершин в дереве.

Следующие $n - 1$ строк содержат по два целых числа $u_{S,i}$ и $v_{S,i}$ ($1 \le u_{S,i}, v_{S,i} \le n$), описывающих ребра дерева $S$.

Следующие $n - 1$ строк содержат по два целых числа $u_{T,i}$ и $v_{T,i}$ ($1 \le u_{T,i}, v_{T,i} \le n$), описывающих ребра дерева $T$.

Гарантируется, что сумма $n$ по всем наборам данных в одном файле не превышает $2 \times 10^5$.

Выходные данные

Для каждого набора данных выведите одну строку с целым числом — количеством пар, удовлетворяющих условию.

Примеры

Входные данные 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

Выходные данные 1

1
2
2
12