Solar system

The planets in a solar system have entered into a number of very complicated customs unions. Each customs union consists of a continuous interval of planets, where the customs union $[a, b]$ consists of all planets between the $a$-th and $b$-th, counted from the sun.

Your friend Zorgax runs a large logistics company that handles interplanetary transports. Every time the company makes a transport between two planets, they must go through a customs process for each customs union they enter or exit between the two planets. However, if a certain customs union lies strictly between the start and end points of the journey, the transport does not have to go through that customs union; they simply fly over all the planets that are part of that union.

For each transport, Zorgax must first determine which entry and exit processes the transport must undergo. This is very time-consuming, so he has asked for your help.

Zorgax has planned $Q$ different trips, where each trip goes between two planets. For each planned trip, print the number of entry and exit customs processes the transport must undergo.

Input

The first line contains the number of customs unions $N$ ($1 \le N \le 10^5$).

This is followed by $N$ lines, one for each customs union. The $i$-th of these contains two integers, $1 \le l_ i \leq r_ i \le 10^9$. This means there is a customs union that consists of all planets $j$ where $l_ i \leq j \leq r_ i$, where the planets are numbered according to their distance from the sun.

Next, there is a line with the number of planned trips $Q$ ($1 \le Q \le 10^5$).

Finally, there are $Q$ lines, one for each trip. Each line consists of two integers $1 \le a \neq b \le 10^9$ – the planets from which the trip starts and ends, respectively.

Output

Print a single integer for each trip – the number of entry and exit customs processes the transport must undergo.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample 2

In example case $2$, there are five customs unions. Of these, planet $1$ is part of the first and fourth unions, and planet $10$ is part of the first and fifth unions. The trip between planet $1$ and $10$ thus requires two customs processes: first when the transport leaves planet $1$ and the fourth union, and another when it arrives at planet $10$ and enters the fifth union. The second and third unions lie strictly between the two planets, so the transport never needs to enter either of these unions. Therefore, the answer is $2$.

2
1 3
2 3
1
3 1

1

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

2
2

4
4 10
7 11
14 14
18 22
3
10 2
3 8
11 20

2
2
2

5
4 7
16 18
14 16
7 13
2 10
3
3 8
11 20
4 7

1
1
1