暂无测试数据。

六年级二班正在进行班长竞选，候选者为：蒜头君、花椰妹。

老师呼吁尽可能多的学生参与投票，因此投票会持续一天的时间。现在设有两个投票箱：

• 如果支持蒜头君，则需要在第一个投票箱内投入一票；
• 如果支持花椰妹，则需要在第二个投票箱内投入一票；

所有的学生都非常遵守规则，即：每一人只会投一票，要么投给蒜头君，要么投给花椰妹。

在这一天中，老师按照时间顺序查看过 $N$ 次投票箱内的情况。第 $i$ 次查看，可以知道蒜头君和花椰妹的得票的最简整数比为 $a_i : b_i$（保证 $a_i$ 和 $b_i$ 互为质数），在任意时刻，两人的得票数均 $>0$，且每个人的得票数只可能增加或保持不变，不可能减少。

你需要通过老师 $N$ 次查看的最简整数比，计算出最终最少有多少人参与了投票。

知识提醒：

1. 比是由一个前项和一个后项组成的除法算式，只不过把“÷”（除号）改成了“:”（比号）而已，是除法另一种表现方式。但除法算式表示的是一种运算，而比则表示两个数的关系。举一个例子，比如 6 ÷ 4 用比的形式写作 6 : 4。最简整数比是指比的前后皆是整数且为互质数，例如：6 : 4 = (6 / 2) : (4 / 2) = 3 : 2。
2. 如果 $a,b$ 互为质数，那么 $a,b$ 的最大公约数等于 $1$。可以通过 algorithm 头文件中的 __gcd(a, b) 求解 $a, b$ 的最大公约数。

输入格式

第一行输入一个正整数 $N$，表示老师查看的次数。

接下来输入 $N$ 行，每行两个以空格隔开的正整数 $a_i, b_i$，表示第 $i$ 次查看时，蒜头君和花椰妹得票的最简整数比 $a_i : b_i$。

输出格式

输出一个正整数，表示通过老师 $N$ 次查看的最简整数比，计算出最终的最少参与投票的人数。

数据范围

对于 $100\%$ 的数据，$1\leq N \leq 20, 1\leq a_i, b_i \leq 100$，且 $a_i,b_i$ 互为质数，且最终的答案在 int 范围内。

3
2 3
1 1
3 2

10

4
1 1
1 1
1 5
1 100

101