A 和 B 正在准备编程竞赛。
A和B学习的大学是一组由走廊连接的房间。总的来说,大学有 n 个房间,由 n-1 个走廊连接,这样你就可以通过沿着走廊从任何一个房间到达任何另一个房间。房间编号为 1 到 n。
每天 A 和 B 在大学的一些房间里进行比赛,每次比赛结束后他们都会聚集在同一个房间里讨论问题。 A 和 B 希望讨论问题的房间和进行竞赛的房间之间的距离相等。两个房间之间的距离是它们之间最短路径上的边数。
当他们每天在新的房间里进行竞赛时,他们要求你帮助他们找到接下来 m 天的每一天可能讨论问题的房间数量。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 大学的房间数。
接下来的 n - 1 行描述走廊。其中第 i 行 (1 ≤ i ≤ n - 1) 包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n),表明第 i 条走廊连接房间 ai 和 bi。
下一行包含整数 m (1 ≤ m ≤ 105) — 查询数。
接下来的 m 行描述查询。这些行中的第 j 行 (1 ≤ j ≤ m) 包含两个整数 xj 和 yj (1 ≤ xj, yj ≤ n),这意味着在第 j 天,A 将在房间 xj 中写入比赛,B 将在房间 yj 中写入。
输出
在第 i (1 ≤ i ≤ m) 行中打印与第 i 天 A 和 B 进行比赛的房间等距离的房间数。
示例
输入 #1
4 1 2 1 3 2 4 1 2 3
输出 #1
1
输入 #2
4 1 2 2 3 2 4 2 1 2 1 3
输出 #2
0 2
注意
在第一个样本中,只有一个房间与 2 号和 3 号房间的距离相同 - 1 号房间。