AT_ttpc2023_m Sum is Integer

$ 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} $ は整数である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ q_1 $ $ p_2 $ $ q_2 $ $ \vdots $ $ p_N $ $ q_N $

答えを出力せよ。

### 部分点 - 追加の制約 $ q_i \le 30\ (1\le i\le N) $ を満たすデータセットに正解した場合は $ 20 $ 点が与えられる。 ### Sample Explanation 1 条件を満たす $ (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 $ となっています。このケースは部分点の制約を満たしています。 ### Sample Explanation 2 $ 1\le l\le r\le 5 $ を満たすすべての整数の組 $ (l,r) $ が条件を満たします。このケースも部分点の制約を満たしています。 ### Sample Explanation 3 $ \displaystyle\sum_{i=1}^{2}\dfrac{p_i}{q_i}=\dfrac{1}{99999}+\dfrac{99999}{100000}=\dfrac{9999900001}{9999900000}=1.00000000010000100001... $ は整数ではありません。 このケースは部分点の制約を満たしていません。 ### Constraints - 入力はすべて整数 - $ 1\le N\le 2\times 10^5 $ - $ 1\le p_i\le q_i\le 10^5\ (1\le i\le N) $