Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math

k=int(input())

sum=0
for l in range(k):
    for m in range(k):
        for n in range(k):
            tmp=l+1
            tmp=math.gcd(tmp,m+1)
            tmp=math.gcd(tmp,n+1)
            sum+=tmp

print(sum)




### FIXED CODE ###

import math

k=int(input())

sum=0
for l in range(k):
    for m in range(k):
        tmp=math.gcd(l+1,m+1)
        for n in range(k):
            gcd=math.gcd(tmp,n+1)
            sum+=gcd

print(sum)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ts = [(x, y) for x in range(-2, 3)
      for y in range(-2, 3) if not (x, y) in moves and (x, y) != (0, 0)]

grid = [list(map(str, input().rstrip())) for _ in range(h)]

q = deque([(sx, sy)])
qq = deque([(sx, sy)])

grid[sx][sy] = 0

while len(q) > 0 or len(qq) > 0:
    while q:
        (cx, cy) = q.popleft()
        for m in moves:
            nx, ny = cx + m[0], cy + m[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy]
                    q.append((nx, ny))
                elif grid[nx][ny] == "#":
                    qq.append((cx, cy))
    while qq:
        (cx, cy) = qq.popleft()
        for t in ts:
            nx, ny = cx + t[0], cy + t[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy] + 1
                    q.append((nx, ny))

print(grid[gx][gy] if grid[gx][gy] != "." else -1)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ts = [(x, y) for x in range(-2, 3)
      for y in range(-2, 3) if not (x, y) in moves and (x, y) != (0, 0)]

grid = [list(map(str, input().rstrip())) for _ in range(h)]

q = deque([(sx, sy)])
qq = deque([(sx, sy)])

grid[sx][sy] = 0

while len(q) > 0 or len(qq) > 0:
    while q:
        (cx, cy) = q.popleft()
        for m in moves:
            nx, ny = cx + m[0], cy + m[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy]
                    q.append((nx, ny))
                elif grid[nx][ny] == "#":
                    qq.append((cx, cy))
    while qq:
        (cx, cy) = qq.popleft()
        for t in ts:
            nx, ny = cx + t[0], cy + t[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy] + 1
                    q.append((nx, ny))

print(grid[gx][gy] if grid[gx][gy] != "." else -1)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-1)
### BUGGY CODE ###

from itertools import groupby
from heapq import heapify, heappop

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]

sushi.sort(key=lambda x: (x[1], x[0]), reverse=True)

maxs = []
rems = []
kinds = set()
for k, g in groupby(sorted(sushi[:K], key=lambda x: x[0]), key=lambda x: x[0]):
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    rems.extend(d)
    kinds.add(k)
heapify(rems)
ans = sum(maxs) + sum(rems) + len(kinds)**2

for k, g in groupby(sushi[K:], key=lambda x: x[0]):
    if not rems:
        break
    if k in kinds:
        continue
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    heappop(rems)
    kinds.add(k)
    ans = max(ans, sum(maxs) + sum(rems) + len(kinds)**2)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)

score = 0

remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    kinds.add(t)
    score += d
score += len(kinds)**2

test = score
for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    rm = remains.pop()
    test = test + (d - rm) + (len(kinds)*2 - 1)
    score = max(score, test)

print(score)
### BUGGY CODE ###

def main():
  import numpy as np
  n,k=map(int,input().split())
  a=np.array(list(map(int,input().split())))
  k=k if k<50 else 50
  for _ in range(k):
    b=np.zeros(n+1,dtype=int)
    for i in range(n):
      ai=a[i]
      l=0 if i-ai<0 else i-ai
      r=n if i+ai+1>n else i+ai+1
      b[l]+=1
      b[r]-=1
    for i in range(n-1):
      b[i+1]+=b[i]
    a=b[:-1]
    if min(a)==n:
      break
  print(*a)
if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
from itertools import accumulate
def main():
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  k=k if k<50 else 50
  for _ in range(k):
    b=[0]*(n+1)
    for i in range(n):
      ai=a[i]
      l,r=i-ai,i+ai+1
      l=0 if l<0 else l
      r=n if r>n else r
      b[l]+=1
      b[r]-=1
    b=tuple(accumulate(b))[:-1]
    a=b
    if min(set(b))==n:
      break
  print(*a)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import bisect

N=int(input())
A=list(map(int,input().split()))
A.sort()

ans=0
for i in range(N-2):
	for j in range(i+1,N-1):
		p = A[i]+A[j]
		ans += bisect.bisect_left(A[j+1:],p)

print(ans)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = [int(x) for x in input().split()]
L.sort()

ans = 0
for i in range(N-2):
	for j in range(i+1,N-1):
		ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

s = int(input())
n = len(str(s))
slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)
cnt = [0]*2019

for m in slist:
    cnt[m] += 1

ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

print(ans)


### FIXED CODE ###

s = input()[::-1]
a = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
for c in s:
    a += int(c) * d
    a %= 2019
    d *= 10
    d %= 2019
    cnt[a] += 1

#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

print(ans)
### BUGGY CODE ###

import copy

n = int(input())
x = [int(num) for num in input().split()]
xx = sorted(x)

for i in range(n):
    x_ =copy.copy(xx) 
    x_.remove(x[i])
    b = x_[n//2 - 1]
    print(b)

### FIXED CODE ###

n = int(input())
x = [int(num) for num in input().split()]
xx = sorted(x)

mid_l = xx[n//2 -1]
mid_r = xx[n//2]

for _ in x:
    if _ <= mid_l:
        print(mid_r)
    else:
        print(mid_l)
### BUGGY CODE ###

from bisect import insort_left
n, m = map(int, input().split())
d = [[] for _ in range(n + 1)]
m = [tuple(map(int, input().split())) for _ in range(m)]

for p, y in m:
    insort_left(d[p], y)

for i, row in enumerate(d):
    d[i] = {x: i+1 for i, x in enumerate(row)}

for p, y in m:
    print('{:06}{:06}'.format(p, d[p][y]))

### FIXED CODE ###

from bisect import bisect_left
from collections import defaultdict
n, m = map(int, input().split())
m = [tuple(map(int, input().split())) for _ in range(m)]

d = defaultdict(list)
for p, y in sorted(m):
    d[p] += [y]


for p, y in m:
    i = bisect_left(d[p], y)
    print('{:06}{:06}'.format(p, i+1))
### BUGGY CODE ###

#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

INF = 10**9+7
N = II()
pow = 1
for i in range(1, N+1):
    pow *= i
print(pow%INF)

### FIXED CODE ###

#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

INF = 10**9+7
N = II()
pow = 1
for i in range(1, N+1):
    pow = pow*i%INF
print(pow)
### BUGGY CODE ###

from collections import deque

n, k = map(int, input().split())
H = list(map(int, input().split()))

deqh = deque(H)

for i in range(k):
    if len(deqh) == 0:
        break
    max_hp = max(deqh)
    deqh.remove(max_hp)

print(sum(deqh))


### FIXED CODE ###

from collections import deque
import sys

n, k = map(int, input().split())
H = list(map(int, input().split()))

if k >= n:
    print("0")
    sys.exit(0)

H.sort()
print(sum(H[0:len(H) - k]))
### BUGGY CODE ###

S = input()
K = int(input())
ans = ''
for s in S:
    if 123 - ord(s) <= K and s != 'a':
        ans += 'a'
        K -= 123-ord(s)
    else:
        ans += s
if K > 0:
    ans = ans[:-1] + chr((ord(ans[-1])+K-97) % 26+ord('a'))
print(ans)


### FIXED CODE ###

def main():
    S = input()
    K = int(input())
    ans = ''
    for s in S:
        if 123 - ord(s) <= K and s != 'a':
            ans += 'a'
            K -= 123-ord(s)
        else:
            ans += s
    if K > 0:
        ans = ans[:-1] + chr((ord(ans[-1])+K-97) % 26+97)
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import*
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return Counter(divisors)

n,*a=map(int,open(0).read().split())
ans=Counter()
for i in range(n):
    ans+=dv(a[i])
l=[]
for k,v in ans.items():
    if v==n-1 or v==n:
        l.append(k)
print(max(l))

### FIXED CODE ###

from collections import*
from functools import*
from fractions import*
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return Counter(divisors)

n,*a=map(int,open(0).read().split())
if n<1000:
    ans=Counter()
    for i in range(n):
        ans+=dv(a[i])
    l=[]
    for k,v in ans.items():
        if v==n-1 or v==n:
            l.append(k)
    print(max(l))
else:
    print(max(reduce(gcd,a[n//4:]),reduce(gcd,a[:n//4]+a[n//2:]),reduce(gcd,a[:n//2]+a[3*n//4:]),reduce(gcd,a[:3*n//4])))
### BUGGY CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))

visited = [0]
flag = False
loopStart = 0
loopCycle = 0
currentTown = 0

for i in range(n):
    currentTown = a[visited[-1]]-1
    if currentTown in visited:
        flag = True
        loopStart = visited.index(currentTown)
        loopCycle = i + 1 - loopStart
        break
    if i == k - 1:
        print(currentTown+1)
        break

    visited.append(currentTown)

if flag:
    print(visited[loopStart + (k - loopStart) % loopCycle]+1)

### FIXED CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))

visited = [0]
visitedSet = {0}
flag = False
loopStart = 0
loopCycle = 0
currentTown = 0

for i in range(n):
    currentTown = a[visited[-1]]-1
    if currentTown in visitedSet:
        flag = True
        loopStart = visited.index(currentTown)
        loopCycle = i + 1 - loopStart
        break
    if i == k - 1:
        print(currentTown+1)
        break

    visited.append(currentTown)
    visitedSet.add(currentTown)

if flag:
    print(visited[loopStart + (k - loopStart) % loopCycle]+1)
### BUGGY CODE ###

N, Q = [int(i) for i in input().split()]
S = input()

output = []
for i in range(Q):
    s, t = [int(i) for i in input().split()]
    string = S[s-1:t]
    cnt = 0
    for j in range(len(string)):
        partial_string = string[j:j+2]
        if partial_string == 'AC':
            cnt += 1
    output.append(cnt)

for _ in output:
    print(_)

### FIXED CODE ###

N, Q = [int(i) for i in input().split()]
S = input()

t = [0] * (N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)
    
for i in range(Q):
    l, r = [int(i) for i in input().split()]
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

S = input()

cands = ["dream", "dreamer", "erase", "eraser"]
searched = {}

queue = [""]
find_flag = 0
while len(queue) != 0:
    s = queue.pop(0)
    searched[s] = 1
    if s == S:
        find_flag = 1
        break
        
    s_ = cands[0]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)

    s_ = cands[1]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)
        
    s_ = cands[2]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)
        
    s_ = cands[3]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)

if find_flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()

candidates = ["dream", "dreamer", "erase", "eraser"]

find_flag = 0
rest_S = S
while True:
#     print(rest_S[-5:], rest_S[-7:]) 
    if len(rest_S) == 0:
        find_flag = 1
        break
    elif (len(rest_S) >= 7) & (rest_S[-7:] in candidates):
        rest_S = rest_S[:-7]
    elif (len(rest_S) >= 6) & (rest_S[-6:] in candidates):
        rest_S = rest_S[:-6]
    elif (len(rest_S) >= 5) & (rest_S[-5:] in candidates):
        rest_S = rest_S[:-5]
    else:
        break

if find_flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)


def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if i == st:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)


def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if st <= i < st + lt:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))

sum_p = []

for i in range(N - K + 1):
    sum_p.append(sum(p[i:i+K]))
    

ex = 0

for x in range(1,max(sum_p)-K+2):
    ex += x / (max(sum_p)-K+1)

print(ex + K - 1)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))

sum_p = 0

for i in range(K):
    sum_p += p[i]

max_p = sum_p

for j in range(K,N):
    sum_p -= p[j - K]
    sum_p += p[j]
    max_p = max(max_p,sum_p)

ex = (max_p - K + 2)/2

print(ex + K - 1)
### BUGGY CODE ###

INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for l in range(N * 1000 + 1):
        if l - value[i - 1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i - 1]] + weight[i - 1])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for l in range(N * 1000 + 1):
        if l - value[i - 1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i - 1]] + weight[i - 1])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)
### BUGGY CODE ###

import os
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main():
    n = int(input())
    count = math.pow(3,n)

    result = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            for l in range(1,n+1):
                result += gcd(i,j,l)

    print(result)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import os
from math import gcd


def main():
        k = int(input())
        result = 0
        for i in range(1,k+1):
                for j in range(1,k+1):
                        t = gcd(i,j)
                        for l in range(1,k+1):
                                result += gcd(t,l)
        print(result)
    

if __name__ == "__main__":
    main()
### BUGGY CODE ###

"""
N = int(input())
A = list(map(int,input().split()))
ans = 0
mod = 1000000007

for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i]*A[j]
        ans = ans%mod
print(ans)
"""
from collections import deque

N,M = map(int,input().split())
MAP = [[False for x in range(N+1)] for x in range(N+1)]
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    MAP[A][B]=True
    MAP[B][A]=True
LIST = list(range(1,N+1))

while(True):
    if(LIST != []):
        group = set()
        group.add(LIST[0])
        q = deque()
        q.append(LIST[0])
        while(len(q) != 0):
            a = q.popleft()
            MAP[:][a] = ""
            for i in range(N+1):
                if(MAP[a][i]):
                    q.append(i)
                    group.add(i)
                    try:
                        LIST.remove(i)
                    except:
                        pass
                MAP[a][i] = ""
        if(ans < len(group)):
            ans = len(group)
    else:
        break
print(ans)


### FIXED CODE ###

from collections import Counter

class UnionFind:
    def __init__(self,num:int):
        self.r = [-1 for i in range(num)]
    def root(self,x:int):
        if(self.r[x] < 0):
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    def unite(self,x:int,y:int):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return False
        if(self.r[rx] > self.r[ry]):
            rx,ry = ry,rx
        self.r[rx] += self.r[ry]
        self.r[ry] = rx
        return True
    def size(self,x:int):
        return -self.r[self.root(x)]

N,M = map(int,input().split())
group = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    group.unite(A-1,B-1)
ans = 0
for i in range(N):
    ans = max(ans,group.size(i))
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
B = []
for i in range(N) :
    in_a,in_b = map(int,input().split())
    A.append(in_a)
    B.append(in_b)
    
for i in range(1,N) :
    a = A[i]
    b = B[i]
    while ((A[i-1] > a) or (B[i-1] > b)) :
        a += A[i]
        b += B[i]
    A[i] = a
    B[i] = b
ans = A[-1] + B[-1]
print(ans)


### FIXED CODE ###

N = int(input())
A = []
B = []
for i in range(N) :
    in_a,in_b = map(int,input().split())
    A.append(in_a)
    B.append(in_b)
    
for i in range(1,N) :
    if A[i-1] > A[i] :
        if A[i-1] % A[i] == 0 :
            a = A[i-1]//A[i]
        else :
            a = A[i-1]//A[i] + 1
    else :
        a = 1
    
    if B[i-1] > B[i] :
        if B[i-1] % B[i] == 0 :
            b = B[i-1]//B[i]
        else :
            b = B[i-1]//B[i] + 1
    else :
        b = 1
    
    p = max(a,b)
    
    A[i] *= p
    B[i] *= p

ans = A[-1] + B[-1]

print(ans)