给定 $2N$ 个正整数 $(p_1, q_1, p_2, q_2, \dots, p_N, q_N)$。

请找出满足以下条件的整数对 $(l, r)$ 的数量：

• $1 \le l \le r \le N$
• $\sum_{i=l}^{r} \frac{p_i}{q_i}$ 是一个整数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $p_1 \ q_1$ $p_2 \ q_2$ $\vdots$ $p_N \ q_N$

• 输入中的所有值均为整数。
• $1 \le N \le 2 \times 10^5$
• $1 \le p_i \le q_i \le 10^5$ ($1 \le i \le N$)

输出格式

输出答案。

样例

样例 1

4
1 6
1 3
1 2
1 2

样例 1 输出

2

样例 2

5
1 1
2 2
3 3
4 4
5 5

样例 2 输出

15

样例 3

2
1 99999
99999 100000

样例 3 输出

0

说明

在第一个样例中，有两对 $(l, r)$ 满足条件：$(l, r) = (1, 3), (3, 4)$。实际上：

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

在第二个样例中，所有满足 $1 \le l \le r \le 5$ 的整数对 $(l, r)$ 都满足条件。

在第三个样例中，$\sum_{i=1}^{2} \frac{p_i}{q_i} = \frac{1}{99999} + \frac{99999}{100000} = \frac{9999900001}{9999900000} = 1.00000000010000100001\dots$ 不是一个整数。