In a police investigation, ~n~ suspects were identified and now it's up to the witnesses to try to find the perpetrator. The height of every suspect ~i~ was measured, but due to the unreliability of measurement, it is known only that their height is a real number from the interval from ~l_i~ to ~r_i~ (inclusive). At most one of the suspects is the perpetrator, and it could be the case that none of them are.

A single lineup consists of choosing two positive integers ~a~ and ~b~ ~(1 \le a \le b \le n)~, then taking the suspects ~a, a+1, \dots, b~ to a separate room so that the witnesses could try to identify the perpetrator. As the witnesses could be confused if two of the suspects have the same height, a lineup is allowed only if it is possible to guarantee that no two suspects will have the same height. During a lineup, the witnesses will always be able to identify the perpetrator if he is among the chosen suspects, or they will be able to tell that he is not among them.

The lead investigator is now interested in answering questions of the following form: "If I were certain that the label of the perpetrator could only be between ~p~ and ~q~ ~(p \le q)~, what is the minimum number of lineups needed in the worst case so that the witnesses are able to find the perpetrator, or report that he is not among the suspects?" Help the lead investigator answer ~q~ of such questions.

Input Specification

The first line contains a positive integer ~n~, the number of suspects.

The following ~n~ lines contain two positive integers ~l_i~ and ~r_i~ ~(1 \le l_i \le r_i \le 10^9)~ which represent the possible height range of the suspect with label ~i~.

The next line contains a positive integer ~q~, the number of questions.

The following ~q~ lines contain two positive integers ~p_i~ and ~q_i~ ~(1 \le p_i \le q_i \le n)~ which determine a question.

Output Specification

In ~q~ lines print the answers to the corresponding questions: the minimum required number of lineups.

Constraints

In every subtask, it holds that ~1 \le n, q \le 200\,000~.

Subtask	Points	Constraints
1	10	~q = 1, p_1 = 1, q_1 = N~
2	10	~1 \le n \le 5000, 1 \le q \le 5000~
3	20	~1 \le n \le 5000, 1 \le q \le 200\,000~
4	20	~1 \le n \le 200\,000, 1 \le q \le 100~
5	50	No additional constraints.

Sample Input 1

2
1 1
1 1
3
1 1
2 2
1 2

Sample Output 1

1
1
2

Sample Input 2

3
1 1
2 2
3 3
3
1 1
2 3
1 3

Sample Output 2

1
1
1

Sample Input 3

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

Sample Output 3

3
1
3

Explanation for Sample Output 3

For the first and the third question, it is sufficient to have three lineups: one consists of the suspect ~1~, one consists of the suspects ~2~ and ~3~, and one consists of the suspects ~4~ and ~5~.

For the second question, it is sufficient to have one lineup which consists of the suspects ~3~, ~4~, and ~5~.