給定兩棵包含 $n$ 個點的樹 $S$ 和 $T$，節點的編號均為 $1$ 到 $n$，根節點均為 $1$ 號點。計算有多少個二元組 $(x, y)$ 滿足 $x < y$ 且 $\text{LCA}_S(x, y) = \text{LCA}_T(x, y)$。

† $\text{LCA}_S(x, y)$ 代表樹 $S$ 中 $x$ 和 $y$ 兩點的最近公共祖先，即一個離根最遠的節點 $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