仙界有一个园子，园中 $n$ 棵智慧树排成一行，依次编号为 $1$ 到 $n$.

每棵智慧树都会周期性地结出智慧果。第 $i$ 棵树每 $m_i$ 年结一次果，且今年离下次结果还有 $b_i$ 年。

现在要求你回答 $q$ 个问题，均形如：

• 对于第 $l$ 至 $r$ 棵智慧树构成的序列，有多少个连续子序列，使得子序列中的树在某一年能同时结出智慧果？

输入格式

第一行一个正整数 $n$, 表示有 $n$ 棵智慧树。

接下来 $n$ 行，第 $i$ 行两个整数 $m_i, b_i$, 意义如题中所述。

接下来一行一个正整数 $q$, 表示有 $q$ 个问题。

接下来 $q$ 行，每行两个整数 $l, r$, 表示一个问题，具体意义如题中所述。

输出格式

输出 $n$ 行，每行一个整数，表示每个问题的答案。

样例一

input

4
4 1
3 2
2 0
6 0
4
1 1
2 3
2 4
1 4

output

1
3
5
7

限制与约定

设 $\max_{i=1}^n\{m_i\}=M$.

对于全部数据，$1\le n, q, M\le10^6$, $\forall 1\le i\le n$, $0\le b_i < m_i$, $1\le m_i\le M$.

子任务一（$10$ 分）：$n, q\le100$, $M\le20$;

子任务二（$10$ 分）：$n, q\le1000$, $M\le20$;

子任务三（$20$ 分）：$n, q\le10^5$, $M\le20$;

子任务四（$30$ 分）：$n, q, M\le10^5$, $\forall1\le i\le n$, $m_i$ 均为素数；

子任务五（$30$ 分）：无特殊限制。