在一次警察调查中，确定了 $n$ 名嫌疑人，现在需要证人来找出罪犯。每名嫌疑人 $i$ 的身高都经过了测量，但由于测量的不确定性，只知道他们的身高是区间 $[l_i, r_i]$（包含端点）内的一个实数。最多有一名嫌疑人是罪犯，也可能他们都不是。

一次“列队”（lineup）包括选择两个正整数 $a$ 和 $b$（$1 \le a \le b \le n$），然后将嫌疑人 $a, a+1, \dots, b$ 带到一个单独的房间，以便证人尝试识别罪犯。由于如果两名嫌疑人身高相同，证人可能会感到困惑，因此只有在能够保证没有两名嫌疑人身高相同的情况下，才允许进行列队。在列队期间，如果罪犯在被选中的嫌疑人中，证人总是能够识别出罪犯，或者他们能够判断出罪犯不在其中。

首席调查员现在想回答以下形式的问题：“如果我确定罪犯的编号只能在 $p$ 和 $q$ 之间（$p \le q$），那么在最坏情况下，为了让证人能够找到罪犯，或者报告他不在嫌疑人中，最少需要多少次列队？”请帮助首席调查员回答 $q$ 个这样的问题。

输入格式

第一行包含一个正整数 $n$，表示嫌疑人的数量。

接下来的 $n$ 行，每行包含两个正整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$），表示编号为 $i$ 的嫌疑人的身高范围。

下一行包含一个正整数 $q$，表示问题的数量。

接下来的 $q$ 行，每行包含两个正整数 $p_i$ 和 $q_i$（$1 \le p_i \le q_i \le n$），确定了一个问题。

输出格式

输出 $q$ 行，每行输出对应问题的答案：最少需要的列队次数。

子任务

在每个子任务中，满足 $1 \le n, q \le 200\,000$。

样例

输入格式 1

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

输出格式 1

1
1
2

输入格式 2

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

输出格式 2

1
1
1

输入格式 3

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

输出格式 3

3
1
3

说明

第三个样例的说明： 对于第一个和第三个问题，三次列队就足够了：一次包含嫌疑人 1，一次包含嫌疑人 2 和 3，一次包含嫌疑人 4 和 5。 对于第二个问题，一次包含嫌疑人 3、4 和 5 的列队就足够了。