题目描述

白板上写着 $N$ 个整数 $a_1, a_2, \\ldots, a_N$。其中，$a_i$ 可以表示为 $a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}}$，其中 $m_i$ 为质数个数 $p_{i,1} < p_{i,2} < \ldots < p_{i,m_i}$，$e_{i,1}, e_{i,2}, \ldots, e_{i,m_i}$ 为正整数。
你需要选择其中一个整数，并将其替换为 $1$。
请找出在替换之后，这 $N$ 个整数的最小公倍数可能的数量。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq m_i$
• $\sum{m_i} \leq 2 \times 10^5$
• $2 \leq p_{i,1} < p_{i,2} < \ldots < p_{i,m_i} \leq 10^9$
• $p_{i,j}$ 为质数。
• $1 \leq e_{i,j} \leq 10^9$
• 输入中的所有值都是整数。

输入

输入格式如下：

$N$

$m_1$

$p_{1,1}$ $e_{1,1}$

$\vdots$

$p_{1,m_1}$ $e_{1,m_1}$

$m_2$

$p_{2,1}$ $e_{2,1}$

$\vdots$

$p_{2,m_2}$ $e_{2,m_2}$

$\vdots$

$m_N$

$p_{N,1}$ $e_{N,1}$

$\vdots$

$p_{N,m_N}$ $e_{N,m_N}$

输出

输出答案。

示例输入1

4
1
7 2
2
2 2
5 1
1
5 1
2
2 1
7 1

示例输出1

3

白板上的整数分别为 $a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14$。
如果你将 $a_1$ 替换为 $1$，白板上的整数变为 $1,20,5,14$，它们的最小公倍数是 $140$。
如果你将 $a_2$ 替换为 $1$，白板上的整数变为 $49,1,5,14$，它们的最小公倍数是 $490$。
如果你将 $a_3$ 替换为 $1$，白板上的整数变为 $49,20,1,14$，它们的最小公倍数是 $980$。
如果你将 $a_4$ 替换为 $1$，白板上的整数变为 $49,20,5,1$，它们的最小公倍数是 $980$。
因此，替换之后的 $N$ 个整数的最小公倍数可以为 $140$、$490$ 或 $980$，所以答案是 $3$。

示例输入2

1
1
998244353 1000000000

示例输出2

1

白板上可能有很大的整数。