问题描述

给定一棵树，树上有 $n$ 个结点，结点编号为 $1 \sim n$ 。 再给定 $q$ 次询问，每次询问给定 $2$ 个结点编号，请编程计算出这两个结点在树上的距离。

输入格式

第一行一个正整数 $n$，表示结点数量； 接下来 $n−1$ 行，每行两个整数 $x,y$ 表示 $x,y$ 之间有一条连边； 然后一个整数 $q$，表示有 $q$ 个询问； 接下来 $q$ 行每行两个整数 $x,y$ 表示询问 $x$ 到 $y$ 的距离。 数据范围： $1≤n,q≤10^5$，$1≤x,y≤n$；

输出格式

输出 $q$ 行，每行一个整数，表示每次询问的答案。

样例

输入

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

输出

3
4