该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

你知道吗，Allen在机房睡了一暑假的地铺！

Allen有一棵$n$个节点的树，有$q$个查询，每个查询给出两个节点$u, v$，你需要输出在删除节点$u$及其所连边的情况下，节点$v$所在的连通块的大小。

每个询问之间是独立的。也就是说，每次询问不会真的删除节点$u$。

请回忆：一棵$n$个节点的树是一个含有$n$个点，$n-1$条边的无向连通图。

输入格式

第一行输入一个正整数$n\ (1 \le n \le 3 \times 10^5)$，代表给定树的节点数量。

接下来输入$n-1$行，每行给出2个正整数$u, v\ (1 \le u, v \le n, u \ne v)$，代表存在一条边连接节点$u, v$。保证给定的图形成一棵树。

接下来输入一个正整数$q\ (1 \le q \le 3 \times 10^5)$，代表询问的个数。

接下来输入$q$行，每行2个正整数$u, v\ (1 \le u, v \le n, u \ne v)$，代表给定的询问。

输出格式

输出$q$行。每行输出1个整数，代表在删除节点$u$及其所连边的情况下，节点$v$所在的连通块大小。

样例

5
1 2
1 3
2 4
2 5
3
1 2
2 3
4 1

3
2
4

提示

对于第一个询问，$u = 1, v = 2$，删除1号节点及其所连边后，2号节点所在的连通块为$\{2,4,5\}$，故输出3。