The land of carrot trees is a magical ~~land~~ tree with nodes and edges, rooted at node . One day, a lonely carrot decides to ask queries of the form `n d`

: the number of unordered pairs of nodes that have a depth between and have node as their **lowest common ancestor**. Note that these pairs may include the node itself and the pair may be two of the same node. Also note that this can be larger than the height of the subtree from . Can you help the poor carrot with these queries?

**Note:** The **lowest common ancestor** of nodes and is the furthest node from the root that is on the path from to the root *and* on the path from to the root.

#### Constraints

For all subtasks, and .

##### Subtask 1 [10%]

##### Subtask 2 [20%]

##### Subtask 3 [70%]

#### Input Specification

The first line will have , the number of nodes.

The next lines will have two integers, and , indicating that there is an edge from to .

The next line will have , the number of queries that follow.

The next lines will have two space separated integers, and , the and values for the query.

#### Output Specification

The answer to each query, each on a new line.

#### Sample Input

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

#### Sample Output

```
28
28
7
14
20
```

#### Explanation for Sample

For the third query for example, the unordered pairs are .

## Comments