Harryxun/stf_run huggingface dataset:
from math import gcd
N = 1000001
sieve = [-1] * (N + 1)
sieve[0] = sieve[1] = 0
for i in range(N + 1):
    if sieve[i] != -1:
        continue
    else:
        index = i * i
        while True:
            if index > N:
                break
            sieve[index] = i
            index += i

isCounted = [0] * 1000001
isPairwiseCoprime = True
M = int(input())
A = list(map(int,input().split()))
for i in range(M):
    elem = A[i]
    primeList = []
    while sieve[elem] != -1:
        primeList.append(sieve[elem])
        elem //= sieve[elem]
    primeList.append(elem)
    for elem1 in primeList:
        if isCounted[elem1] != 0:
            isPairwiseCoprime = False
            break
    if not isPairwiseCoprime:
        break
    for elem1 in primeList:
        isCounted[elem1] += 1
if isPairwiseCoprime:
    print("pairwise coprime")
else:
    curGcd = A[0]
    for elem in A:
        curGcd = gcd(elem,curGcd)
    if curGcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")


### FIXED CODE ###

from math import gcd
N = 1000001
sieve = [-1] * (N + 1)
sieve[0] = sieve[1] = 0
for i in range(N + 1):
    if sieve[i] != -1:
        continue
    else:
        index = i * i
        while True:
            if index > N:
                break
            sieve[index] = i
            index += i

isCounted = [0] * 1000001
isPairwiseCoprime = True
M = int(input())
A = list(map(int,input().split()))
for i in range(M):
    elem = A[i]
    if elem == 1:
        continue
    primeList = []
    while sieve[elem] != -1:
        primeList.append(sieve[elem])
        elem //= sieve[elem]
    primeList.append(elem)
    for elem1 in primeList:
        if isCounted[elem1] != 0:
            isPairwiseCoprime = False
            break
    if not isPairwiseCoprime:
        break
    for elem1 in primeList:
        isCounted[elem1] += 1
if isPairwiseCoprime:
    print("pairwise coprime")
else:
    curGcd = A[0]
    for elem in A:
        curGcd = gcd(elem,curGcd)
    if curGcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(100000)  # RecursionError対策

"""解説
(1) まず、赤いボールをN-K個一列に並べる

(2) 赤いボールと赤いボールの隙間をi箇所選んで、そこに青いボールをK個置くことを考える

 R R R R R
0 1 2 3 4 5

    この選び方は、(N-K+1)C(i)通り

(3) それぞれの選び方について、青いボールをそれぞれの隙間に何個割り当てるかを考える。
    それぞれ1個以上割り当てる必要があるので、決め方は(K-1)C(i-1)通り。


[入力例1]
B B B R R

・i=1
Bの塊を挿入する位置は、
 R R  |  R R  |  R R
^     |   ^   |     ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において1通り

よって、3*1 = 3通り


・i=2
 R R  |  R R   |  R R
^ ^   | ^   ^  |   ^ ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において、

- 少なくとも1個ずつ分配すると、自由におけるBの数は1個
- 2箇所に玉1つを分配する場合の数は
(2)C(1) = 2通り

よって3*2 = 6通り

・i=3
 R R
^ ^ ^
の1通り


[重複組み合わせの考え方]
http://www7b.biglobe.ne.jp/~math-tota/suA/tamahako.htm

B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
B-i個の玉と、i-1個の区切りの重複組み合わせ。

・6個の玉を、区別のできる3つの箱に分ける場合の数
6個の玉と、2個のしきりの重複組み合わせ

○○○○|○○| (4,2,0)の場合
|○○|○○○○ (0,2,4)の場合

「8個のオブジェクトのうち、2個を選んでしきりにする」と同じなので、(8)C(2) = 28

"""
from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

def solve():
    N, K = list(map(int, input().split()))
    B, R = K, N-K
    MOD = 10**9+7

    for i in range(1, K+1):
        # R+1から、i個選ぶ
        ans = combination_formula(R+1, i)
        if B-i == 0:
            print(ans%MOD)
            continue
        # B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
        # B-i個の玉と、i-1個の区切りの重複組み合わせ。
        ans *= combination_formula(B-i+i-1, i-1)%MOD
        print(ans%MOD)



if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(100000)  # RecursionError対策

"""解説
(1) まず、赤いボールをN-K個一列に並べる

(2) 赤いボールと赤いボールの隙間をi箇所選んで、そこに青いボールをK個置くことを考える

 R R R R R
0 1 2 3 4 5

    この選び方は、(N-K+1)C(i)通り

(3) それぞれの選び方について、青いボールをそれぞれの隙間に何個割り当てるかを考える。
    それぞれ1個以上割り当てる必要があるので、決め方は(K-1)C(i-1)通り。


[入力例1]
B B B R R

・i=1
Bの塊を挿入する位置は、
 R R  |  R R  |  R R
^     |   ^   |     ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において1通り

よって、3*1 = 3通り


・i=2
 R R  |  R R   |  R R
^ ^   | ^   ^  |   ^ ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において、

- 少なくとも1個ずつ分配すると、自由におけるBの数は1個
- 2箇所に玉1つを分配する場合の数は
(2)C(1) = 2通り

よって3*2 = 6通り

・i=3
 R R
^ ^ ^
の1通り


[重複組み合わせの考え方]
http://www7b.biglobe.ne.jp/~math-tota/suA/tamahako.htm

B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
B-i個の玉と、i-1個の区切りの重複組み合わせ。

・6個の玉を、区別のできる3つの箱に分ける場合の数
6個の玉と、2個のしきりの重複組み合わせ

○○○○|○○| (4,2,0)の場合
|○○|○○○○ (0,2,4)の場合

「8個のオブジェクトのうち、2個を選んでしきりにする」と同じなので、(8)C(2) = 28

"""
from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

def solve():
    N, K = list(map(int, input().split()))
    B, R = K, N-K
    MOD = 10**9+7

    for i in range(1, K+1):
        if R+1-i < 0:
            print(0)
            continue
        
        # R+1から、i個選ぶ
        ans = combination_formula(R+1, i)
        if B-i == 0:
            print(ans%MOD)
            continue
        # B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
        # B-i個の玉と、i-1個の区切りの重複組み合わせ。
        if B-i+i-1-(i-1) >= 0:
            ans *= combination_formula(B-i+i-1, i-1)%MOD
        print(ans%MOD)



if __name__ == "__main__":
    solve()
from fractions import gcd
from functools import reduce

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return int(x*y/gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lambda a, b : lcm(a, b), A)
for i in range(N):
    B[i] = int(global_lcm/A[i])
ans = 0
for i, b in enumerate(B):
    ans += b
    ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce, lru_cache

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return int(x*y)//int(gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A) % MOD
ans = 0
for i in range(N):
    ans += (global_lcm*pow(A[i], MOD-2, MOD)) % MOD
    ans %= MOD

print(ans)
def mx(ls,i):
    rls = ls[:]
    if i <= 0 or len(rls) == 0: return 0
    else     : return (i+1)*rls.pop()+ mx(rls,i-1)

def cns(ls,m,sm):
    global n, s
    count = 0
    if m == n:
        if sm == s: return 1
        else      : return 0
    elif s <= sm + mx(ls,n-m) and sm <= s:
        for i in range(9-m+1):
            rls = ls[:]
            k = rls.pop(i)
            count += cns(rls,m+1,sm+(m+1)*k)
        return count
    else: return 0

ls = [0,1,2,3,4,5,6,7,8,9]
while True:
    n, s = map(int, raw_input().split())
    if s > mx(ls,n): print 0
    else        : print cns(ls,0,0)

### FIXED CODE ###

def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break
x1, y1, x2, y2 = map(int, input().split())
if x1 == x2:
  if y1 < y2:
    d = y2 - y1
    x3, y3 = x2-d, y2
    x4, y4 = x1-d, y1
  else:
    d = y1 - y2
    x3, y3 = x2+d, y2
    x4, y4 = x1+d, y1
else:
  if x1 < x2:
    d = x2 - x1
    x3, y3 = x2, y2+d
    x4, y4 = x1, y1+d
  else:
    x3, y3 = x2, y2-d
    x4, y4 = x1, y1-d

print(x3, y3, x4, y4)

### FIXED CODE ###

x1, y1, x2, y2 = map(int, input().split())
v1 = [x2 - x1, y2 - y1]
v = [-v1[1], v1[0]]

x3, y3 = x2 + v[0], y2 + v[1]
x4, y4 = x1 + v[0], y1 + v[1]

print(x3, y3, x4, y4)
s = input()
if s = "SUN":
  print ("7") 
elif s= "MON":
  print ("6")
elif s= "TUE":
  print ("5")
elif s= "WED":
  print ("4")
elif s= "THU":
  print ("3")
elif s= "FRI":
  print ("2")
else:
  print("1")


### FIXED CODE ###

s = input()
days = {"SUN":7,"MON":6,"TUE":5,"WED":4,"THU":3,"FRI":2,"SAT":1}
print (days[s])
n = int(input())
L = [input() for i in range(n)]
kekka = 0
for i in range(n):
  if 2*L[i] > sum(L):
    kekka = 1
    break
    
if kekka == 1:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
kekka = 0
for i in range(n):
  if 2*L[i] >= sum(L):
    kekka = 1
    break
    
if kekka == 1:
  print('No')
else:
  print('Yes')
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2,n):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        if h == h2[i][0] and (h != 0 and h2[i][0] != 0):
            ans = min(ans,c+h2[i][1])
        else:
            continue
        break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = [INF] * 10000

    for i in range(1,2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        if h1[dif] > tc: h1[dif] = tc

    ans = h1[0]

    for i in range(1,2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        if dif == 0:
            ans = min(ans,tc)
        else:
            ans = min(ans,h1[dif]+tc)

    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()
import math

a,b=map(int,input().split())

print(int((a*b)/math.gcd(a, b)))

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

a,b=map(int,input().split())
print(lcm(a,b))
def examD():
    n = I(); s = I()
    ans = -1
    if s==n:
        ans = n+1
    else:
        loop = int(n**(0.5))
        for i in range(2,loop+1):
            cur = n
            ansC = 0
            while cur>0:
                ansC += cur%i
                cur = cur//i
            if ansC==s:
                ans = i
                break
    if ans==-1:
        for p in range(loop,0,-1):
            bcandi = (n-s)/p + 1
            ansC = n%bcandi + n//bcandi
            if ansC==s:
                ans = int(bcandi)
                break
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

### FIXED CODE ###

def examD():
    def f(b, n):
        if n < b:
            return n
        else:
            return f(b, n // b) + n % b
    n = I(); s = I()
    ans = -1
    if s==n:
        ans = n+1
    else:
        loop = int(n**(0.5))
        for b in range(2,loop+1):
            if f(b,n)==s:
                ans = b
                break
    if ans==-1:
        for p in range(loop+1,0,-1):
            b = (n-s)//p + 1
            if b >= 2 and f(b,n)==s:
                    ans = b
                    break

    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
Card=[list(map(int,input().split())) for i in range(3)]
N=int(input())
b=[int(input()) for i in range(N)]
for i in range(N):
    for j in range(3):
        for k in range(3):
            if A[j][k]==b[i]:
                A[j][k]=0
if (A[0][0]==A[0][1]==A[0][2]==0) or (A[1][0]==A[1][1]==A[1][2]==0) or (A[2][0]==A[2][1]==A[2][2]==0) or (A[0][0]==A[1][0]==A[2][0]==0) or (A[0][1]==A[1][1]==A[2][1]==0)  or (A[0][2]==A[1][2]==A[2][2]==0) or (A[0][0] == A[1][1] == A[2][2] == 0) or (A[2][0]==A[1][1]==A[0][2]==0):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

card=[list(map(int,input().split())) for i in range(3)]
N=int(input())
b=[int(input()) for i in range(N)]
for i in range(N):
    for j in range(3):
        for k in range(3):
            if card[j][k]==b[i]:
                card[j][k]=0
if (card[0][0]==card[0][1]==card[0][2]==0) or (card[1][0]==card[1][1]==card[1][2]==0) or (card[2][0]==card[2][1]==card[2][2]==0) or (card[0][0]==card[1][0]==card[2][0]==0) or (card[0][1]==card[1][1]==card[2][1]==0)  or (card[0][2]==card[1][2]==card[2][2]==0) or (card[0][0] == card[1][1] == card[2][2] == 0) or (card[2][0]==card[1][1]==card[0][2]==0):
    print('Yes')
else:
    print('No')
n = int(input())
x = input()
y = input()
place = 0
if x[0]==y[0]: num,flag = 3,True
else: num,flag = 6,False
while place<n-1:
	if flag:
		place += 1
		num = (num*2)%(10**9+7)
		if x[place]!=y[place]: flag = False
	else:
		place += 2
		if x[place]==y[place]: flag=True
		else: num=(num*3)%(10**9+7)
print(num)

### FIXED CODE ###

n = int(input())
x = input()
y = input()
if x[0]==y[0]: num,flag,place = 3,True,1
else: num,flag,place = 6,False,2
while place!=n:
	if flag:
		num = (num*2)%(10**9+7)
		if x[place]!=y[place]:
			flag = False
			place += 2
		else: place+=1
	else:
		if x[place]==y[place]:
			flag = True
			place += 1
		else:
			num = (num*3)%(10**9+7)
			place += 2
print(num)
n, m = list(map(int,input().split()))

penalty = 0

corrected = {}
wa = {}

for i in range(m):
  pi, si = input().split()
  if (si == 'AC' and not corrected.get(pi)):
    corrected[pi] = True
  elif (si == 'WA' and not corrected.get(pi)):
    wa[pi] += wa[pi]

correct = len(corrected.keys())
for i in corrected.keys()
	penalty += wa[i]

print("{} {}".format(correct, penalty))
    


### FIXED CODE ###

n, m = list(map(int,input().split()))

penalty = 0

corrected = {}
wa = {}

for i in range(m):
  pi, si = input().split()
  if (si == 'AC' and not corrected.get(pi)):
    corrected[pi] = True
  elif (si == 'WA' and not corrected.get(pi)):
    wa[pi] = wa[pi] + 1 if wa.get(pi) else 1

correct = len(corrected.keys())
for i in corrected.keys():
	penalty += wa[i] if  wa.get(i) else 0

print("{} {}".format(correct, penalty))
l = int(input())

result = []
for i in range(1,10**3):
    for j in range(i, 10**3):
        if l-i-j > 0:
            result.append(i*j*(l-i-j))
print(max(result))

### FIXED CODE ###

l = int(input())

print((l**3)/27)
import math

S = input().split()
A = int(S[0])
B = int(S[1])
C = int(S[2])
D = int(S[3])

E = int((C * D) / math.gcd(C, D))

X = (B//C)-(A-1//C)
Y = (B//D)-(A-1//D)
Z = (B//(E))-(A-1//(E))

print(int(B-A+1-X-Y+Z))

### FIXED CODE ###


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 #最小公倍数


def lcm(a, b):
    return a*b//gcd(a, b)


S = input().split()
A = int(S[0])
B = int(S[1])
C = int(S[2])
D = int(S[3])

E = lcm(C, D)

X = int(B//C)-int((A-1)//C)
Y = int(B//D)-int((A-1)//D)
Z = int(B//E)-int((A-1)//E)

print(B-A+1-X-Y+Z)
n = int(input())
print(int(a+a**2+a**3))

### FIXED CODE ###

n = int(input())   
print(int(n+n**2+n**3))
S = input()
if S = 'ABC':
    print('ARC')
else:
    print('ABC')

### FIXED CODE ###

S = input()
if S == 'ABC':
    print('ARC')
else:
    print('ABC')
N = int(input())
H = list(map(int, input().split()))
ans = []
a = 0

if N == 1:
    print('0')
    exit()

for i in range(N-2):
    if H[t] >= H[t+1]:
        a += 1
    else:
        a = 0
    ans.append(a)

print(max(ans))


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = []
a = 0

if N == 1:
    print('0')
    exit()

for i in range(N-1):
    if H[i] >= H[i+1]:
        a += 1
    else:
        a = 0
    ans.append(a)

print(max(ans))
N,K=map(int,input())
P=sorted(list(map(int,input().split())))
print(sum(P[:K]))

### FIXED CODE ###

N,K=map(int,input().split())
P=sorted(list(map(int,input().split())))
print(sum(P[:K]))
a_yen , b_yen, c_yen , a_count,b_count = map(int,input().split())

abmax = max(a_count, b_count)
c_count = 0
kouhopiza = a_yen * a_count + b_yen * b_count + c_yen * c_count

while c <= 2*abmax:
    if kouhopiza > a_yen * a_count + b_yen * b_count + c_yen * c_count and a_count > -1 and b_count > -1:
        kouhopiza = a_yen * a_count + b_yen * b_count + c_yen * c_count
    c_count = c_count + 2
    a_count = a_count - 1
    b_count = b_count - 1





### FIXED CODE ###

a_yen , b_yen, c_yen , a_count,b_count = map(int,input().split())

abmax = max(a_count, b_count)
c_count = 0
kouhopiza = a_yen * a_count + b_yen * b_count + c_yen * c_count

while c_count <= 2*abmax:
    if kouhopiza > a_yen * a_count + b_yen * b_count + c_yen * c_count and a_count > -1 and b_count > -1:
        kouhopiza = a_yen * a_count + b_yen * b_count + c_yen * c_count
    elif a_count > -1 and b_count < 0:
        if kouhopiza > a_yen * a_count + c_yen * c_count:
            kouhopiza = a_yen * a_count + c_yen * c_count
    elif a_count < 0 and b_count > -1:
        if kouhopiza > b_yen * b_count + c_yen * c_count:
            kouhopiza = b_yen * b_count + c_yen * c_count
        
    c_count = c_count + 2
    a_count = a_count - 1
    b_count = b_count - 1
print(kouhopiza)
n,x=map(int,input().split())
a=sorted(list(map(int,input().split())))
s=a[0]
i=0
while s<=x and i<n:
  i+=1
  s+=a[i]
print(i)

### FIXED CODE ###

n,x=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(n):
  x=x-a[i]
  if x<0:
    break
if i==n-1 and x==0:
  i+=1
print(i)
# -*- coding: utf-8 -*-

import matplotlib

a = list(input().split())
A = list(input().split())

count = 0
for i in range(0, a[2]):
    if(A[i] < a[2]):
        count = count + 1


if(count > (A.shape[0] -  count)):
        count = A.shape[0] -  count

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-

a = input().split()
A = input().split()

for i in range(0, len(a)):
    a[i] = int(a[i])

for i in range(0, len(A)):
    A[i] = int(A[i])

count = 0
for i in range(0, len(A)):
    if(A[i] < a[2]):
        count = count + 1


if(count > (len(A) -  count)):
        count = len(A) -  count

print("{0}".format(count))
import sys
sys.setrecursionlimit(100000)

def DFS(i):
    if done[i]:
        ans[-1]+=1
        done[i]=False
        for g in G[i]:
            if done[g]:
                DFS(g)
    else:
        return p

N,M=map(int,input().split())
G=[[] for _ in range(N)]
done=[True for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=[]
for j in range(N):
    ans.append(0)
    if done[j]:
        DFS(j)
print(max(ans))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def DFS(i):
    if done[i]:
        ans[-1]+=1
        done[i]=False
        for g in G[i]:
            if done[g]:
                DFS(g)
    else:
        return p

N,M=map(int,input().split())
G=[[] for _ in range(N)]
done=[True for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=[]
for j in range(N):
    ans.append(0)
    if done[j]:
        DFS(j)
print(max(ans))
from collections import deque
def main():
    N=int(input())
    A = [deque(map(int, input().split())) for _ in range(N)]

    days = 0
    changed = True
    played = set()
    while changed:
        played.clear()
        changed = False
        for i in range(N-1):
            if len(A[i]) == 0:
                continue
            a1 = A[i][0]
            if len(A[a1-1]) == 0:
                continue
            a2 = A[a1-1][0]
            if a1 in played or a2 in played:
                continue
            if a2-1 == i:
                A[a2-1].popleft()
                A[a1-1].popleft()
                played.add(a2)
                played.add(a1)
                changed = True
        if changed:
            days+=1

    for a in A:
        if len(a) > 0:
            print(-1)
            break
    else:
        print(days)

if __name__ == '__main__':
    main()

### FIXED CODE ###

S=input()
T=input()
ans=0
for s,t in zip(S,T):
  if s==t:
    ans+=1
print(ans)
X, Y = list(map(int, input().split()))

def f(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a
def nCr(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= f(a, p)
    c *= pow(f(b, p), p - 2, p)
    c *= pow(f(a - b, p), p - 2, p)
    return c % p

if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or Y > X*2 or X > Y*2:
  print(0)
else:
  m = (2*X-Y)//3
  n = (2*Y-X)//3
  print(nCr(m+n, n))


### FIXED CODE ###

X, Y = list(map(int, input().split()))

def nCr(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or Y > X*2 or X > Y*2:
  print(0)
else:
  m = (2*X-Y)//3
  n = (2*Y-X)//3
  print(nCr(m+n, n))
import sys
W, H, x, y = map(int, input().split())

area = max(min((W - x) * H, x * H), min((H - y) * W, y * W))

num = 0

if (x, y) == (0, 0) or (x, y) == (W, H) or (x, y) == (W, 0) or (x, y) == (0, H):
    print((W * H) / 2, 0)
    sys.exit()

#直線上も加えよう
if abs(W / x) == abs(H / y) or y == H - (H / W) * x:
    print(W * H / 2, 0)
    sys.exit()
    


if min((W - x) * H, x * H) == min((H - y) * W, y * W):
    num = 1
else:
    num = 0

print(area, num)

### FIXED CODE ###

from decimal import *
import sys
W, H, x, y = map(int, input().split())
num = 0
if 2 * x == W and 2 * y == H:
    num = 1

print(W * H / 2, num)
N=int(input())

X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])


def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)


a=X[0][0]
b=X[0][1]

def f(a,b,i):
  c=X[i+1][0]
  d=X[i+1][1]

  x=ceil(a/c)
  y=ceil(b/d)

  if i!=N-2:


    ans=100000000000
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,f(a,b,i+1))
    
  
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,f(a,b,i+1))
    
    return ans


  elif i==N-2:

    ans=100000000
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,a+b)
    
  
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,a+b)

    return ans



print(f(a,b,0))





### FIXED CODE ###

N=int(input())
 
X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])
 
 
a=X[0][0]
b=X[0][1]
 
for i in range(1,N):
  c=X[i][0]
  d=X[i][1]
 

  x= (a + (c - 1)) // c
  y= (b + (d -1)) // d
  
  a1=1000000000000000000
  b1=1000000000000000000
  a2=1000000000000000000
  b2=1000000000000000000
  if d*x-b>=0:
    a1=c*x
    b1=d*x
 
  
  if c*y-a>=0:
    a2=c*y
    b2=d*y
  if (a1+b1)<(a2+b2):
    a=a1
    b=b1
  else:
    a=a2
    b=b2
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" a1 = "+str(a1)+" b1 = "+str(b1)+" a2 = "+str(a2)+" b2 = "+str(b2)+" c = "+str(c)+" d = "+str(d))
  
 
 
 
 
  
print(a+b)