Background

徐老师开办了一所学校，里面有 $n（\le2\times10^5）$ 名学生。

Description

年终晚会上，徐老师决定让所有学生做一个游戏。

每名学生先去抽一个数 $m$ ，表示有 $m$ 轮抽（得）数（分）机会。

每一轮需要抽两次，第一次先到一个质数箱里面抽取一个质数 $p$ ，然后再到普通箱子里面抽个正整数 $k$ 。保证两个箱子中最大的数都不超过$10^9$。这一轮该学生的得分为 $p^k$ 。

一共进行 $m$ 轮，该学生总的得分是每一轮得分的乘积。输入数据保证同一名学生抽取了 $m$ 个不同的质数。

由于时间有限，所有学生总的抽奖轮次不超过 $2\times10^5$ 。

学校的总分是礼堂内每一名学生的分数的最小公倍数。

为了保持学校礼堂的整洁，规定不能在礼堂内吃喝拉撒。因此，经常会有一名学生跑到礼堂外。

那么问题来了，假设每一名学生都轮流出过一次礼堂（剩下 $n-1$ 名学生在礼堂内），那么可以得到 $n$ 个学校得分，如果把这些得分丢到一个集合中，问该集合的基是多少？

Format

Input

第一行有一个正整数 $n$ ，表示接下来会按顺序给出 $n$ 名学生的得分快照。

每名学生的快照格式如下：

第一行给出一个正整数 $m$，表示该学生总共进行了 $m$ 轮抽数。

接下来的 $m$ 行，每行给出两个正整数 $p$ 和 $k$，表示每一轮抽到的质数和指数。

Output

在一行中输出答案。

Samples

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

4

Limitation

1s, 1024KiB for each test case.