$n$ 個の頂点を持つ2つの木 $S$ と $T$ が与えられる。頂点の番号はどちらも $1$ から $n$ までであり、根はどちらも頂点 $1$ である。$x < y$ かつ $\text{LCA}_S(x, y) = \text{LCA}_T(x, y)$ を満たす組 $(x, y)$ がいくつあるか計算せよ。

$\text{LCA}_S(x, y)$ は、木 $S$ における $x$ と $y$ の最近共通祖先、すなわち $x$ と $y$ の両方の祖先である頂点のうち、根から最も遠い頂点 $z$ を表す。

入力

各テストファイルには複数のテストケースが含まれる。最初の行にテストケースの数 $T$ ($1 \le T \le 2 \times 10^4$) が与えられる。各テストケースの形式は以下の通りである。

1行目に整数 $n$ ($2 \le n \le 2 \times 10^5$) が与えられ、木の頂点数を表す。 続く $n - 1$ 行には、それぞれ2つの整数 $u_{S,i}$ と $v_{S,i}$ ($1 \le u_{S,i}, v_{S,i} \le n$) が与えられ、木 $S$ の辺を表す。 続く $n - 1$ 行には、それぞれ2つの整数 $u_{T,i}$ と $v_{T,i}$ ($1 \le u_{T,i}, v_{T,i} \le n$) が与えられ、木 $T$ の辺を表す。

各テストファイルにおいて、すべてのテストケースの $n$ の総和は $2 \times 10^5$ を超えないことが保証される。

出力

各テストケースについて、条件を満たす組の数を1行で出力せよ。

入出力例

入力 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