提示: 欢迎访问OurACM平台。
Problem 1753 Another Easy Problem

Accept: 463    Submit: 2031
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

小TT最近学习了高斯消元法解方程组,现在他的问题来了,如果是以下的方程,那么应该如何解呢?

C(n1,m1)==0 (mod M)

C(n2,m2)==0 (mod M)

C(n3,m3)==0 (mod M)

................

C(nk,mk)==0 (mod M)

小TT希望你告诉他满足条件的最大的M

其中C(i,j)表示组合数,例如C(5,2)=10,C(4,2)=6...

Input

输入数据包括多组,每组数据的第一行是一个正整数T(1<=T<=150)表示接下来描述的T个方程

接下来T行,每行包括2个正整数ni,mi (1<=mi<=ni<=100000)

Output

输出一行答案,表示满足方程组的最大M。

Sample Input

3 100 1 50 1 60 1

Sample Output

10

Source

FZU 2009 Summer Training IV--Number Theory

Submit  Back  Status  Discuss