問題文

2N 個の正整数 (p_1,q_1,p_2,q_2,\dots ,p_N,q_N) が与えられます。

1\le l\le r\le N を満たす整数の組 (l,r) であって、次の条件を満たすものの個数を求めてください。

• \displaystyle\sum_{i=l}^{r}\dfrac{p_i}{q_i} は整数である。

制約

• 入力はすべて整数
• 1\le N\le 2\times 10^5
• 1\le p_i\le q_i\le 10^5\ (1\le i\le N)

部分点

• 追加の制約 q_i \le 30\ (1\le i\le N) を満たすデータセットに正解した場合は 20 点が与えられる。

入力例 1

4
1 6
1 3
1 2
1 2

出力例 1

2

条件を満たす (l,r) は (1,3),(3,4) の 2 つです。実際、

• \displaystyle\sum_{i=1}^{3}\dfrac{p_i}{q_i}=\dfrac{1}{6}+\dfrac{1}{3}+\dfrac{1}{2}=1
• \displaystyle\sum_{i=3}^{4}\dfrac{p_i}{q_i}=\dfrac{1}{2}+\dfrac{1}{2}=1

となっています。このケースは部分点の制約を満たしています。

入力例 2

5
1 1
2 2
3 3
4 4
5 5

出力例 2

15

1\le l\le r\le 5 を満たすすべての整数の組 (l,r) が条件を満たします。このケースも部分点の制約を満たしています。

入力例 3

2
1 99999
99999 100000

出力例 3

0

\displaystyle\sum_{i=1}^{2}\dfrac{p_i}{q_i}=\dfrac{1}{99999}+\dfrac{99999}{100000}=\dfrac{9999900001}{9999900000}=1.00000000010000100001... は整数ではありません。

このケースは部分点の制約を満たしていません。