小婷老师提出了若干组关于子树叶子的查询。每组数据给出一棵以顶点 $1$ 为根的无向树。在根确定以后，没有孩子的顶点称为叶子。

每次询问给出两个顶点 $x$ 和 $y$。需要从以 $x$ 为根的子树中选择一个叶子，再从以 $y$ 为根的子树中选择一个叶子。两次选择互相独立，因此即使两棵子树重叠，也仍然分别进行选择；如果选到同一个叶子，也算一种合法的有序选择方案。

请计算每次询问共有多少种不同的有序选择方案。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组数据的第一行输入一个整数 $N$，表示树的顶点数量。

接下来 $N-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示顶点 $u_i$ 与顶点 $v_i$ 之间有一条边。

随后输入一个整数 $Q$，表示询问次数。

接下来 $Q$ 行，每行输入两个整数 $x$ 和 $y$，描述一次询问。

输出格式

对于每次询问，输出一行一个整数，表示不同有序选择方案的数量。

1
2
1 2
7
2 1
1 1
1 1
1 1
1 2
2 1
2 1

1
1
1
1
1
1
1

3
11
6 5
2 3
5 1
4 2
8 11
7 1
5 9
8 5
2 1
10 3
8
7 2
6 8
2 10
11 8
5 10
10 2
2 5
4 7
7
4 6
2 4
2 1
1 5
7 3
3 2
6
5 1
6 6
5 3
1 7
2 3
5 6
5
2 1
2 5
1 3
4 2
3
3 5
4 1
2 1

2
1
2
1
3
2
6
1
3
1
1
3
2
1
1
3
6

1
12
11 7
11 12
10 4
9 7
3 6
1 2
8 2
5 1
3 1
7 4
1 4
6
10 12
3 8
2 12
5 9
6 12
6 1

1
1
1
1
1
6

数据范围与约定

• $1\le T\le10^4$
• 所有测试组的 $N$ 之和不超过 $2\times10^5$
• 所有测试组的 $Q$ 之和不超过 $2\times10^5$