A graph is defined as a "sea urchin" if it satisfies the following conditions:

1. It is a connected graph.
2. It contains exactly one simple cycle.
3. Every vertex, excluding those on the cycle, has a degree of at most 2.

Given a graph with $n$ vertices and $n$ edges, where the $i$-th edge connects $u_i$ and $v_i$ (the graph is not guaranteed to be connected).

The interval subgraph $[l, r]$ is defined as $(V', E')$, where $E' = \{(u_i, v_i) \mid l \leq i \leq r\}$ and $V' = \{u_i \mid l \leq i \leq r\} \cup \{v_i \mid l \leq i \leq r\}$. In other words, this interval subgraph contains exactly the edges in the interval and all vertices incident to at least one edge in the interval.

There are $q$ queries. For each query given by an interval $[l, r]$, find the number of sub-intervals $[l', r']$ ($l \leq l' \leq r' \leq r$) such that the interval subgraph $[l', r']$ is a sea urchin.

Supplementary note on condition 2:

1. A simple cycle is defined as a path that starts at some vertex, traverses a sequence of distinct edges to return to the starting vertex, contains at least one edge, and visits no vertices more than once except for the start and end vertex. For example, 1-2-3-1 is a simple cycle, and two edges between 1 and 2 form a simple cycle. However, a single vertex is not a cycle, and 1-2-3-4-5-3-1 is not a simple cycle.
2. Condition 2 requires that there are no edges whose endpoints are both on the cycle, other than the edges forming the cycle itself.

Input

The first line contains an integer $n$, representing the number of vertices and edges.

The next $n$ lines each contain two integers $u_i, v_i$, representing an edge.

The next line contains an integer $q$.

The next $q$ lines each contain two integers $l, r$, representing a query.

Output

For each query, output the answer on a single line.

Examples

Input 1

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

Output 1

4
0
3
3
1

Constraints

The data guarantees that there are no self-loops.