白板上的 LCM

题目描述

白板上写有 $N$ 个整数 $a_1,\ldots,a_N$。

这里,$a_i$ 可以用 $m_i$ 个质数 $p_{i,1} \lt \ldots \lt p_{i,m_i}$ 和正整数 $e_{i,1},\ldots,e_{i,m_i}$ 表示为 $a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}}$。

你将选择这 $N$ 个整数中的一个,将其替换为 $1$。

求替换后这 $N$ 个整数的最小公倍数可能取到的值的个数。

输入格式

输入按以下格式从标准输入给出:

N
m_1
p_{1,1} e_{1,1}
⋮
p_{1,m_1} e_{1,m_1}
m_2
p_{2,1} e_{2,1}
⋮
p_{2,m_2} e_{2,m_2}
⋮
m_N
p_{N,1} e_{N,1}
⋮
p_{N,m_N} e_{N,m_N}

输出格式

输出答案。

样例

4
1
7 2
2
2 2
5 1
1
5 1
2
2 1
7 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$。

1
1
998244353 1000000000

1

白板上可能存在巨大的整数。

数据范围

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