Description

给定一棵 $n$ 个点的树。

定义区间 $[l,r]$ 的权值为使编号在 $[l,r]$ 内的所有点连通的最小边数。

有 $q$ 次询问，每次询问给出 $l,r$ ，你需要回答满足 $l \le i < j \le r$ 的所有区间 $[i,j]$ 的权值和。

Format

Input

第一行包含一个正整数 $n$。

接下来 $n$ 行，每行两个正整数 $u,v$ 代表一条树边 $(u,v)$。

第 $n+1$ 行包含一个正整数 $q$。

接下来 $q$ 行，每行两个正整数 $l,r$ 代表一次询问。

Output

共 $q$ 行，每行一个正整数，表示询问的答案。

Samples

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

7
7
3
42
1
27

Limitation

保证对于所有的测试点满足以下限制：$1\leq n,q\leq 10^5,1\leq u,v\leq n,1\leq l\leq r\leq n$。

特殊性质A：保证给定的树是一条链。

特殊性质B：保证存在一个点的度数为 $n-1$。