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

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
import numpy as np
A = np.array(A, np.int64)
ans += np.sum(lcm // A)
ans %= mod
print(ans) 

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
for i in A:
    ans += lcm // i
print(ans % mod)
### BUGGY CODE ###

import functools
import operator

n = input()
li = list(map(int, input().split()))
result = functools.reduce(operator.mul, li)

if result > 10 ** 18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

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

if 0 in li:
  print(0)
else:
  result = 1
  flag = True
  for i in range(n):
    result *= li[i]
    if result > 10 ** 18:
      flag = False
      print(-1)
      break
  if flag == True:
    print(result)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 親の番号 根なら要素数(負の数)

    def find(self, x):
        """木の根を求める"""
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """xとyの属する集合を併合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

N, M, K = map(int, input().split())

l = [[False] * N for _ in range(N)]
pena = [0] * N

uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    l[A][B] = True
    l[B][A] = True
    pena[A] += 1
    pena[B] += 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if not l[C][D] and uf.same(C, D):
        pena[C] += 1
        pena[D] += 1

ans = []

for i in range(N):
    ans.append(uf.size(i) - pena[i] - 1)

print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 親の番号 根なら要素数(負の数)

    def find(self, x):
        """木の根を求める"""
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """xとyの属する集合を併合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

N, M, K = map(int, input().split())

uf = UnionFind(N)
ans = [0] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    ans[A] -= 1
    ans[B] -= 1

for i in range(N):
    ans[i] += uf.size(i) - 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        ans[C] -= 1
        ans[D] -= 1

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

n, m = map(int, input().split())
H = list(map(int, input().split()))
road = [0 for i in range(m)]

for i in range(m):
    road[i] = list(map(int, input().split()))

ans = 0
for i in range(n):
    flag = 0
    for j in range(m):
        if road[j][0] - 1 == i:
            if H[i] <= H[road[j][1]-1]:
                flag = 1
                break
        if road[j][1]  - 1 == i:
            if H[i] <= H[road[j][0]-1]:
                flag = 1
                break
    if flag == 0:
        ans = ans + 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
H = list(map(int, input().split()))
road = [0 for i in range(m)]
ans = [0] * n

for i in range(m):
    road[i] = list(map(int, input().split()))

for j in range(m):
    if H[road[j][0]-1] < H[road[j][1]-1]:
        ans[road[j][0]-1] = 1
    elif H[road[j][0]-1] > H[road[j][1]-1]:
        ans[road[j][1]-1] = 1
    elif H[road[j][0]-1] == H[road[j][1]-1]:
        ans[road[j][0]-1] = 1
        ans[road[j][1]-1] = 1

total = sum(ans)
print(n-total)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] <= used[v]:
                q.append(u)
                used[u] = max(used[u], used[v] + 1)
print(max(used))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
dp = np.full(N, 10**9, dtype=int)

dp[0] = 0
for i in range(N-1):
    X = min(N - 1, i + K)
    H = A[i]
    dp[i+1:i+X+1] = np.minimum(np.abs(H-A[i+1:i+X+1])+dp[i], dp[i+1:i+X+1])

print(dp[N - 1])


### FIXED CODE ###

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

dp=[100000 for i in range(N)]
dp[0]=0

for i,h_now in enumerate(h):
    if i==0:
        continue
    x=max(0,i-K)
    dp[i]=min([dp_i+abs(h_now-h_i) for dp_i,h_i in zip(dp[x:i],h[x:i])])

print(dp[N-1])
### BUGGY CODE ###

import numpy as np


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    c = np.zeros(n, dtype=np.int)
    for i in range(k):
        b = np.array([ai // 2**i % 2 for ai in a], dtype=np.int)
        if b.sum() % 2:
            b = 1 - b
        c += b * 2**i
    print(*c)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    c = [0] * n
    for i in range(k):
        b = [ai // 2**i % 2 for ai in a]
        if sum(b) % 2:
            b = [1 - bi for bi in b]
        for j in range(n):
            c[j] += b[j] * 2**i
    print(*c)


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

k,s = map(int,input().split())
a = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        a += 1
        
print(a)

### FIXED CODE ###

k,s = map(int,input().split())
a = 0
for x in range(k+1):
  for y in range(k+1):
      if s-(x+y) <= k and s-(x+y) >= 0:
        a += 1
        
print(a)
### BUGGY CODE ###

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

class SegTreeMax:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [0]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = max(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i:
            i = (i-1)//2
            self.nodes[i] = max(self.nodes[2*i+1:2*i+3])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.nodes[k]
        return max(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

segt = SegTreeMax([0]*N)
ans = 0
for h,a in zip(H,A):
    v = segt.query(0,h) + a
    segt.update(h-1,v)
    ans = max(ans, v)
print(ans)

### FIXED CODE ###

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

class SegTreeMax:
    def __init__(self,arr):
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [0]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = max(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i:
            i = (i-1)//2
            self.nodes[i] = max(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.n
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.nodes[k]
        return max(self.query(a,b,2*k+1,l,(l+r)//2), self.query(a,b,2*k+2,(l+r)//2,r))

segt = SegTreeMax([0]*N)
ans = 0
for h,a in zip(H,A):
    v = segt.query(0,h) + a
    segt.update(h-1,v)
    ans = max(ans, v)
print(ans)
### BUGGY CODE ###

import itertools
 
H, N = map(int, input().split())
A = list(map(int, input().split()))
 
ans = 'No'
 
for i in itertools.product([True, False], repeat=N):
    if sum([A[j] for j in range(len(A)) if i[j]]) == H:
        ans = 'Yes'
print(ans)

### FIXED CODE ###

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

total = sum(A)
if total >= H:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

# i < j
# j - i = a[i] + a[j]
# a[i] + i = j - a[j]

count = 0
candidate = []
for i in range(n):
    sa = i - a[i]
    count += candidate.count(sa)
    wa = i + a[i]
    candidate.append(wa)

print(count)


### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(int)
ans = 0
for i in range(n):
    ans += d[i - a[i]]
    d[a[i] + i] += 1

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

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = [[10**10] * (10 ** 5 + 10) for _ in range(N + 1)]

dp[0][0] = 0

#  i:N個目 j:価値

for i, (w, v) in enumerate(x, 1):
    for j in range(10**5 + 1):
        dp[i][j] = dp[i - 1][j]
        if j != 0 and v <= j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w)

for i in range(10 ** 5, -1, -1):
    if dp[-1][i] <= W:
        print(i)
        exit()


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = [[10**10] * (10 ** 5 + 10) for _ in range(N + 1)]

dp[0][0] = 0

#  i:N個目 j:価値

for i, (w, v) in enumerate(x, 1):
    for j in range(10**5 + 1):
        dp[i][j] = dp[i - 1][j]
        if j != 0 and v <= j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w)

for i in range(10 ** 5, -1, -1):
    if dp[-1][i] <= W:
        print(i)
        exit()
### BUGGY CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
f = 0
for _ in range(Q):
  a, *b = input().split()
  f += int(a)
  if a == "2":
    if (int(b[0]) + f) % 2 == 1 :
      S.appendleft(b[1])
    else:
      S.append(b[1])
if  f % 2 == 0 :
  print ("".join(S))
else:
  for i in range(len(S)):
    print (S[-i-1], end="")

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
f = 0
for _ in range(Q):
  a, *b = input().split()
  f += int(a)
  if a == "2":
    if (int(b[0]) + f) % 2 == 1 :
      S.appendleft(b[1])
    else:
      S.append(b[1])
D = list(S)
print ("".join(D) if f % 2 == 0 else "".join(D[::-1]))
### BUGGY CODE ###

dp = [[[False] * 30009 for i in range(4)] for j in range(1009)]
dp[0][0][0]=True
cnt=0
for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k] == False:
                continue
            dp[i+1][j][k] = True
            if(j<=2):
                dp[i+1][j+1][k*10+int(s[i])]=True
for i in range(1000):
    if(dp[n][3][i]==True):
        cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
count = 0
for i in range(1000):
    v = str(i).zfill(3)
    k=0
    for j in range(n):
        if v[k] == s[j]:
            k+=1
        if k==3:
            count+=1
            break

print(count)
### BUGGY CODE ###

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


def main():
    s = input()
    t = s

    while True:
        s = s.replace('ST', '')

        if s == t:
            print(len(s))
            exit()

        t = s


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    from collections import deque

    x = input()
    n = len(x)
    d = deque()

    for i in range(n):
        d.append(x[i])

        if len(d) >= 2 and d[-2] + d[-1] == 'ST':
            d.pop()
            d.pop()

    print(len(d))
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
dp_1 = [float("inf") for i in range(2**n)]
dp_2 = [float("inf") for i in range(2**n)]
dp_1[0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        if i % 2 == 0:
            dp_2[j|c] = min(dp_1[j|c], dp_1[j] + a, dp_2[j|c])
            dp_2[j] = min(dp_1[j], dp_2[j])
        else:
            dp_1[j|c] = min(dp_2[j|c], dp_2[j] + a, dp_1[j|c])
            dp_1[j] = min(dp_2[j], dp_1[j])

print([dp_1[-1], -1][dp_1[-1] == float("inf")])


### FIXED CODE ###

n, m = [int(i) for i in input().split()]
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp[i+1][j|c] = min(dp[i][j|c], dp[i][j] + a, dp[i+1][j|c])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

print([dp[-1][-1], -1][dp[-1][-1] == float("inf")])
### BUGGY CODE ###

import numpy as np
n = int(input())
a =  [int(input()) for i in range(n)]



[print(int(max(set(np.concatenate([a[:i], a[i+1:]]))))) for i in range(n)]

### FIXED CODE ###

import numpy as np
n = int(input())
a =  [int(input()) for i in range(n)]
max_a_num = a.count(max(a))
b = sorted(a, reverse=True)
m1, m2 = b[0], b[1]
for i in range(n):
  if max_a_num == 1:
    if a[i] == m1:
      print(m2)
    else:
      print(m1)
  else:
    print(m2)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if set([S[i], S[j], S[k]]) == {"R", "G", "B"} and j-i != k-j:
                ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N-2):
    for d in range(1, (N-i-1)//2+1):
        if {S[i], S[i+d], S[i+2*d]} == {"R", "G", "B"}:
            ans -= 1

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

n,k = map(lambda x: int(x),input().split())
p = list(map(lambda x: int(x),input().split()))
max = 0
e = list(map(lambda x: (1+x)/2,p))
for i in range(n-k+1):
    if max < sum(e[i:i+k]) :
        max = sum(e[i:i+k])

print(max)


### FIXED CODE ###

n,k = map(lambda x: int(x),input().split())
p = list(map(lambda x: (int(x) + 1)/2,input().split()))
ruiseki = [0]
max = 0
for i in range(n) :
    ruiseki.append(ruiseki[i]+p[i])

for j in range(n - k + 1):
    if max < (ruiseki[j+k] - ruiseki[j]) :
        max = (ruiseki[j+k] - ruiseki[j])


print(max)
### BUGGY CODE ###

R, C, K=map(int, input().split())
math=[[0]*C for _ in range(R)]
for _ in range(K):
  r, c, v=map(int, input().split())
  math[r-1][c-1]=v
  
dp=[[[0]*4 for __ in range(C)] for _ in range(R)]
if math[0][0]>0:
  dp[0][0][1]=math[0][0]+0
  
for j in range(1, C):
  dp[0][j][0]=dp[0][j-1][0]+0
  dp[0][j][1]=max(dp[0][j-1][1], dp[0][j-1][0]+math[0][j])
  dp[0][j][2]=max(dp[0][j-1][2], dp[0][j-1][1]+math[0][j])
  dp[0][j][3]=max(dp[0][j-1][3], dp[0][j-1][2]+math[0][j])
    
for i in range(1, R):
  dp[i][0][0]=max(dp[i-1][0])
  dp[i][0][1]=dp[i][0][0]+math[i][0]
  for j in range(1, C):
    dp[i][j][0]=max(dp[i][j-1][0], max(dp[i-1][j]))
    dp[i][j][1]=max(dp[i][j-1][1], dp[i][j-1][0]+math[i][j], max(dp[i-1][j])+math[i][j])
    dp[i][j][2]=max(dp[i][j-1][2], dp[i][j-1][1]+math[i][j])
    dp[i][j][3]=max(dp[i][j-1][3], dp[i][j-1][2]+math[i][j])
    
print(max(dp[-1][-1]))

### FIXED CODE ###

R, C, K=map(int, input().split())
math=[[0]*C for _ in range(R)]
for _ in range(K):
  r, c, v=map(int, input().split())
  math[r-1][c-1]=v
  
dp=[[[0]*C for __ in range(R)] for _ in range(4)]
if math[0][0]>0:
  dp[1][0][0]=math[0][0]+0
  
for j in range(1, C):
  dp[0][0][j]=dp[0][0][j-1]+0
  dp[1][0][j]=max(dp[1][0][j-1], dp[0][0][j-1]+math[0][j])
  dp[2][0][j]=max(dp[2][0][j-1], dp[1][0][j-1]+math[0][j])
  dp[3][0][j]=max(dp[3][0][j-1], dp[2][0][j-1]+math[0][j])
    
for i in range(1, R):
  dp[0][i][0]=max(dp[0][i-1][0], dp[1][i-1][0], dp[2][i-1][0], dp[3][i-1][0])
  dp[1][i][0]=dp[0][i][0]+math[i][0]
  for j in range(1, C):
    dp[0][i][j]=max(dp[0][i][j-1], max(dp[0][i-1][j], dp[1][i-1][j], dp[2][i-1][j], dp[3][i-1][j]))
    dp[1][i][j]=max(dp[1][i][j-1], dp[0][i][j-1]+math[i][j], max(dp[0][i-1][j], dp[1][i-1][j], dp[2][i-1][j], dp[3][i-1][j])+math[i][j])
    dp[2][i][j]=max(dp[2][i][j-1], dp[1][i][j-1]+math[i][j])
    dp[3][i][j]=max(dp[3][i][j-1], dp[2][i][j-1]+math[i][j])
    
print(max(dp[0][-1][-1], dp[1][-1][-1], dp[2][-1][-1], dp[3][-1][-1]))
### BUGGY CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-1):
                for x in xrange(n-1):
                    if dp[y][x]!=0:
                        old = dp[y][x]
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        if dp[y][x]-old==1:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

### FIXED CODE ###

while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n+1)]for j in range(n+1)]
    for i in range(1,n+1):
        j=0
        line=" "+raw_input()
        for c in line:
            if c == ".":
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            j+=1
    allmax=0
    for i in range(n+1):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax
### BUGGY CODE ###

import heapq

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=[]
heapq.heappush(q,(0,sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
while len(q)!=0:
  c,x,y=heapq.heappop(q)
  cost[y][x]=min(cost[y][x],c)
  for i in range(1,k+1):
    if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
      heapq.heappush(q,(c+1,x+i,y))
    else:
      break
  for i in range(1,k+1):
    if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
      heapq.heappush(q,(c+1,x-i,y))
    else:
      break
  for i in range(1,k+1):
    if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
      heapq.heappush(q,(c+1,x,y+i))
    else:
      break
  for i in range(1,k+1):
    if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
      heapq.heappush(q,(c+1,x,y-i))
    else:
      break
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

### FIXED CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A_set = list(set(A))
result = []
for i in range(len(A_set)):
  if A.count(A_set[i])%2!=0:
    if i in result:
      A.remove(A_set[i])
      continue
    result.append(A_set[i])
  else:
    continue
print(len(result))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
dict = {}
for i in A:
  if i not in dict:
    dict[i] = 1
  else:
    dict[i] += 1
print(len([1 for i in dict.values() if i%2!=0]))
### BUGGY CODE ###

n,m = map(int, input().split())
l = m//n
for i in range(l,0,-1):
  if m % i == 0:
    print(i) 
    break

### FIXED CODE ###

n,m = map(int, input().split())
l = m // n
ans = 0
for i in range(int(m**0.5),0,-1):
  if m % i == 0 and m // i >= n:
    if i > ans: ans = i
    d = m // i
    if  m // d >= n and d > ans: ans = d
print(ans)