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

x=int(input())
ans=ansb=0
f=False
m=int(pow(x,0.2))
a=m
while True:
  b=0
  while pow(a,5)-pow(b,5)>=x:
      if pow(a,5)-pow(b,5)!=x:
          b+=1
      else:
          ans=a
          ansb=b
          f=True
          break
  a+=1
  if f:
    break
else:
    f=False
    for a in range(m//2+1):
        for b in range(a,m//2+2):
            if pow(a,5)+pow(b,5)!=x:
                continue
            else:
                ans=a
                ansb=-b
                f=True
                break
        if f:
            break

print(ans,ansb)

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
x=int(input())
for a in range(-10**3,10**3):
    for b in range(-10**3,a):
        if pow(a,5)-pow(b,5)==x:
            print(a,b)
            exit()
### BUGGY CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			else:
				dp1[j + 1] = dp1[j] if dp1[j] > dp2[j + 1] else dp2[j + 1]

	return dp1[-1]

tc = int(raw_input())
for _ in range(tc):
	print(lcs())

### FIXED CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(raw_input())
	for _ in range(tc):
		print(lcs())
### BUGGY CODE ###

S = input()
T = input()
l = len(S)
flag = "Yes"
for i in range(l):
    for j in range(l):
        if (S[i] == S[j] and T[i] != T[j]):
            flag = "No"
        if (S[i] != S[j] and T[i] == T[j]):
            flag= "No"

print(flag)

### FIXED CODE ###

S = input()
T = input()
l = len(S)
flag = "Yes"
Rs = [-1]*130
Rt = [-1]*130

for i in range(l):
    s = ord(S[i])
    t = ord(T[i])
    if Rs[s] < 0:
        Rs[s] = t
    if Rt[t] < 0:
        Rt[t] = s
    if Rs[s] > 0:
        if Rs[s] != t:
            flag = "No"
    if Rt[t] > 0:
        if Rt[t] != s:
            flag = "No"

print(flag)
### BUGGY CODE ###

N = int(input())

min_total = 100000000000000
for a in range(1, N // 2 + 2):
    b = N / a
    if b.is_integer():
        tmp_a_and_b = a + b
        if tmp_a_and_b < min_total:
            min_total = tmp_a_and_b

print(int(min_total - 2))

            

### FIXED CODE ###

# https://atcoder.jp/contests/abc144/tasks/abc144_c

import math

N = int(input())

mi = -1

for i in range(1, int(math.sqrt(N)) + 1):
    a = i
    if N % a != 0:
        continue

    b = N // a
    count = a + b - 2
    
    if mi <= -1 or mi > count:
        mi = count

print(mi)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import numpy as np

def GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[[pivot,rank]] = A[[rank,pivot]]
        for row in range(len(A)):
            if (row != rank and A[row][col]):
                A[row] ^= A[rank]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

digit = defaultdict(int)
use_digit = []
ans = 0
for j in range(60)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        digit[j] = 1
        use_digit.append(j)

a = np.zeros((N,len(use_digit)), dtype=int)
for i in range(N):
    k = 0
    for j in range(60)[::-1]:
        if digit[j]:
            if A[i]>>j & 1:
                a[i][k] = 1
            else:
                a[i][k] = 0
            k += 1

g = GaussJordan(a,False)

s = np.zeros(len(use_digit),dtype=int)
for i in range(N):
    for j in range(len(use_digit)):
        if g[i][j]==1:
            s ^= g[i]
            break

for k in range(len(s)):
    ans += s[k]*2**(use_digit[k]+1)

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

for i in range(N):
    A[i] &= ~xor

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)
### BUGGY CODE ###

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

doubling_list = [x % m]
t = n * (n - 1) // 2
bit = t.bit_length()
for i in range(n - 1):
    doubling = pow(doubling_list[-1], 2, m)
    doubling_list.append(doubling)


print(sum(doubling_list))

### FIXED CODE ###

n, x, m = map(int, input().split())
result = [x]
for i in range(m):
    y = (result[-1] * result[-1]) % m
    if y in result:
        start = result.index(y)
        end = i
        break
    result.append(y)

loop = result[start:]
a = start
b = (n - a) // len(loop)
c = (n - a) % len(loop)
ans = sum(result[:a]) + (sum(loop) * b) + sum(loop[:c])
print(ans)
### BUGGY CODE ###

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

sum_ls=ls[:n]
rest_ls=ls[n:]
tmp=sum(sum_ls)
mx=tmp
for i in rest_ls:
    tmp=tmp-sum_ls[0]+i
    if tmp>mx:
        mx=tmp
    sum_ls.pop(0)
    sum_ls.append(i)

print((mx+n)/2)

### FIXED CODE ###

k,n=map(int,input().split())
ls=list(map(int,input().split()))
sum_ls=ls[:n]
rest_ls=ls[n:]
tmp=sum(sum_ls)
mx=tmp
for i in range(k-n):
    first=ls[i]
    last=ls[i+n]
    tmp=tmp-first+last
    if mx<tmp:
        mx=tmp


print((mx+n)/2)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
N=int(input())
G=[[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
b=[1]*(N+1)
w=[1]*(N+1)
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
G=[[] for _ in range(N+1)]
for _ in range(N-1):
    x,y=map(int, input().split())
    G[x].append(y)
    G[y].append(x)
b=[1]*(N+1)
w=[1]*(N+1)
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)
### BUGGY CODE ###

# ABC 115 C

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

h = [int(input()) for _ in range(N)]

h.sort()

ans = 1.0e+9

for i in range(N-K+1):
    ans = min(ans, max(h[i:i+K]) - min(h[i:i+K]))

print(ans)


### FIXED CODE ###

# ABC 115 C

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

h = [int(input()) for _ in range(N)]

h.sort()

ans = 1.0e+9

for i in range(N-K+1):
    ans = min(ans, h[i+K-1] - h[i])

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

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

ans = 0
m = 1
for i in range(60):
    bits = sum(((a >> i) & 1 for a in A))
    ans += (bits * (N - bits) * m)
    ans %= MOD
    m <<= 1
print(ans % MOD)


### FIXED CODE ###

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

ans = 0
m = 1
for i in range(60):
    bits = sum((a & m for a in A))
    bits //= m
    ans += (bits * (N - bits) * m)
    ans %= MOD
    m <<= 1
print(ans % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

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

INF = 10 ** 15
dp = [INF] * H
dp[0] = 0
answer = INF
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

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

INF = 10 ** 15
dp = [INF] * (H + 1)
dp[0] = 0

answer = INF
for a, b in AB:
  for i in range(H + 1):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)
        
print(answer)
### BUGGY CODE ###

n=int(input())
s=input().split()
l=[int(i) for i in s]
ll=[0 for i in range(n)]
ll[0]=l[0]
for i in range(1,n):
    ll[i]=ll[i-1]+l[i]
ll=[0]+ll
dic={}
for i in ll:
    if i not in dic.keys():
        dic[i]=1
    else:
        dic[i]+=1
res=0
for i in dic.keys():
    res+=dic[i]*(dic[i]-1)//2
print(res)


### FIXED CODE ###

n=int(input())
s=input().split()
l=[int(i) for i in s]
ll=[0 for i in range(n)]
ll[0]=l[0]
for i in range(1,n):
    ll[i]=ll[i-1]+l[i]
ll=[0]+ll
ll.sort()
now=ll[0]
cnt=1
res=0
for i in range(1,n+1):
    if ll[i]==now:
        cnt+=1
    else:
        res+=cnt*(cnt-1)//2
        cnt=1
        now=ll[i]
res+=cnt*(cnt-1)//2
print(res)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def p(n, k, mod):
  x = 1
  for ik in range(k):
    x *= (n - ik)
    x %= mod
  return x

MAX = 10 ** 9 + 7
def main():
  n, m = map(int, input().strip().split())
  s = 0
  nck = 1
  mpk = 1
  mkpnk = p(m, n, MAX)
  for k in range(0, n+1):
    if 0 < k <= n:
      nck *= (n - (k-1)) * pow(k, MAX-2, MAX) 
      nck %= MAX
    if 0 < k <= m:
      mpk *= (m - (k-1))
      mpk %= MAX
    if 0 < k <= n:
      mkpnk *= pow(m - (k - 1), MAX-2, MAX) 
      mkpnk %= MAX
    s += nck * ( (-1) ** k) * mpk * (mkpnk) ** 2
    s %= MAX
  print(s)
  

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def p(n, k, mod):
  x = 1
  for ik in range(k):
    x *= (n - ik)
    x %= mod
  return x

MAX = 10 ** 9 + 7
def main():
  n, m = map(int, input().strip().split())
  s = 0
  nck = 1
  mpk = 1
  mkpnk = p(m, n, MAX)
  for k in range(0, n+1):
    if 0 < k <= n:
      nck *= (n - (k-1)) * pow(k, MAX-2, MAX) 
      nck %= MAX
    if 0 < k <= m:
      mpk *= (m - (k-1))
      mpk %= MAX
    if 0 < k <= n:
      mkpnk *= pow(m - (k - 1), MAX-2, MAX) 
      mkpnk %= MAX
    s += nck * ( (-1) ** k) * mpk * (mkpnk) ** 2
    s %= MAX
  print(s)
  

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

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")]*N
    dp[0] = 0
    for i in range(N):
        for j in range(1, K+1):
            if i+j < N:
                dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9 for _ in range(N)]
    dp[0] = 0
    for i in range(N):
        for j in range(1, K+1):
            if i+j < N:
                dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])


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

n = int(input())
*A, = map(int, input().split())

# メモ化再帰
DP = [[[-1 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]


def f(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    if i+j+k == 0:
        return 0
    tmp = 0.0
    if i > 0:
        tmp += i*f(i-1, j, k)
    if j > 0:
        tmp += j*f(i+1, j-1, k)
    if k > 0:
        tmp += k*f(i, j+1, k-1)
    tmp += n
    tmp /= i+j+k
    DP[i][j][k] = tmp
    return tmp


i, j, k = A.count(1), A.count(2), A.count(3)
print(f(i, j, k))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

n, c = map(int, input().split())

x = [0 for _ in range(n + 2)]
v = [0 for _ in range(n + 1)]
for i in range(n):
    x[i + 1], v[i + 1] = map(int, input().split())

x[n + 1] = c

left = [0 for _ in range(n + 1)]
right = [0 for _ in range(n + 1)]
left_rev = [0 for _ in range(n + 1)]
right_rev = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    left[i] = left[i - 1] + v[i] - (x[i] - x[i - 1])
    left_rev[i] = left[i] - x[i]
    right[i] = right[i - 1] + v[n - i + 1] - (x[n - i + 2] - x[n - i + 1])
    right_rev[i] = right[i] - (c - x[n - i + 1])

result = 0
for i in range(1, n + 1):
    temp = max( (left[i] + max(right_rev[:n - i + 1])) , (right[i] + max(left_rev[:n - i + 1])) )
    if temp > result:
        result = temp

print(result)

### FIXED CODE ###

n, c = map(int, input().split())

x = [0 for _ in range(n + 2)]
v = [0 for _ in range(n + 1)]
for i in range(n):
    x[i + 1], v[i + 1] = map(int, input().split())

x[n + 1] = c

left = [0 for _ in range(n + 1)]
right = [0 for _ in range(n + 1)]
left_rev = [0 for _ in range(n + 1)]
right_rev = [0 for _ in range(n + 1)]

left_temp = 0
right_temp = 0
for i in range(1, n + 1):
    left[i] = left[i - 1] + v[i] - (x[i] - x[i - 1])
    if left_temp < left[i] - x[i]:
        left_rev[i] = left[i] - x[i]
        left_temp = left_rev[i]
    else:
        left_rev[i] = left_temp
    right[i] = right[i - 1] + v[n - i + 1] - (x[n - i + 2] - x[n - i + 1])
    if right_temp < right[i] - (c - x[n - i + 1]):
        right_rev[i] = right[i] - (c - x[n - i + 1])
        right_temp = right_rev[i]
    else:
        right_rev[i] = right_temp

result = 0
for i in range(1, n + 1):
    result = max( (left[i] + right_rev[n - i]) , (right[i] + left_rev[n - i]) , result )

print(result)
### BUGGY CODE ###

def main():
    # 入力
    n = int(input())

    min_l = 10

    # ccc = 0
    for i in range(1, n+1):
        il = len(str(i))
        if il > min_l:
            break
        # ccc += 1
        if n % i != 0:
            continue
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()


### FIXED CODE ###

def main():
    # 入力
    s = input()

    x = len(s)
    limit = int(x/2)+1 if x % 2 == 0 else int(x/2)+2
    limit2 = int(x/2) if x % 2 == 0 else int(x/2)+1

    n = int(s)

    min_l = 11

    # ccc = 0
    for i in range(1, n+1):
        # ccc += 1
        il = len(str(i))
        if il == limit:
            break
        if n % i != 0:
            continue
        if il == min_l:
            break
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if jl == limit2 or il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()
def main():
    N, M = map(int, input().split())
    dict = {}
    for _ in range(M):
        L, R = map(int, input().split())
        for x in range(L, R+1):
            if x in dict:
                dict[x] += 1
            else:
                dict[x] = 1
    print(sum([1 for k, v in dict.items() if v == M]))
main()

### FIXED CODE ###

n, m = map(int, input().split())
L, R = 1, n
for i in range(m):
    l, r = map(int, input().split())
    L = max(L, l)
    R = min(R, r)
print(max(R-L+1, 0))
### BUGGY CODE ###

from heapq import heappop, heappush
from collections import Counter

N, M, K = list(map(int, input().split()))
edges1 = [[] for _ in range(N + 1)]
edges2 = [[] for _ in range(N + 1)]


A, B = [], []
C, D = [], []
for _ in range(M):
    _a, _b = list(map(int, input().split()))
    A.append(_a)
    B.append(_b)
    edges1[_a].append(_b)
    edges1[_b].append(_a)

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    C.append(_c)
    D.append(_d)
    edges2[_c].append(_d)
    edges2[_d].append(_c)

# print(edges1)
# print(edges2)

def dfs(v):
    visited = [False for _ in range(N + 1)]
    queue = []
    heappush(queue, v)
    visited[v] = True

    counter = 0

    while queue:
        n = heappop(queue)
        for u in edges1[n]:
            if not visited[u]:
                visited[u] = True
                if u not in edges1[v] and u not in edges2[v]:
                    counter += 1
                heappush(queue, u)
    return counter


# all search
ans = []
for v in range(1, N + 1):
    counter = dfs(v)
    ans.append(counter)
print(" ".join(map(str, ans)))

### FIXED CODE ###

from heapq import heappop, heappush
from collections import Counter


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return 
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
    
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


N, M, K = list(map(int, input().split()))
edges1 = [[] for _ in range(N + 1)]
edges2 = [[] for _ in range(N + 1)]
uf = UnionFind(N)

A, B = [], []
C, D = [], []
for _ in range(M):
    _a, _b = list(map(int, input().split()))
    A.append(_a)
    B.append(_b)
    uf.unite(_a, _b)
    edges1[_a].append(_b)
    edges1[_b].append(_a)

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    C.append(_c)
    D.append(_d)
    edges2[_c].append(_d)
    edges2[_d].append(_c)

i, blocked = 1, 0
for b in edges2[1]:
    if uf.is_same_group(i, b):
        blocked += 1
print(uf.count(i) - 1 - len(edges1[i]) - blocked, end='')

for i in range(2, N + 1):
    print(' ', end='')
    blocked = 0
    for b in edges2[i]:
        if uf.is_same_group(i, b):
            blocked += 1
    print(uf.count(i) - 1 - len(edges1[i]) - blocked, end='')
print()
### BUGGY CODE ###

N, M = map(int, input().split())
E = [[] for i in range(M)]
for i in range(M):
  E[i] = [int(x) - 1 for x in input().split()]
cnt = 0
for p in range(1, 2 ** M):
  V = [[] for i in range(N)]
  idx = 0
  while p:
    if p % 2:
      V[E[idx][0]].append(E[idx][1])
      V[E[idx][1]].append(E[idx][0])
    idx += 1
    p //= 2
  if sum([len(v) for v in V]) == 2 * (N - 1) and len(V[0]) == 1:
    P = [0] + V[0]
    while len(V[P[-1]]) == 2:
      P += [V[P[-1]][0] if V[P[-1]][0] != P[-2] else V[P[-1]][1]]
    cnt += 1 if len(P) == N else 0
print(cnt)

### FIXED CODE ###

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
cnt = [0]
def dfs(V, s):
  V[s] = 1
  if sum(V) == N:
    cnt[0] += 1
  else:
    for adj in G[s]:
      if V[adj] == 0:
        dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N, 0)
print(cnt[0])
### BUGGY CODE ###

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

j = 0

for i in range(a,b+1):
    if i % x == 0:
        j += 1

print(j)

### FIXED CODE ###

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

if a % x == 0:
    print(b//x - a//x + 1)

else:
    print(b//x - a//x)
### BUGGY CODE ###

import sys, os, re
from pprint import pprint
from math import sin, cos, sqrt, radians

n, m = list(map(int, sys.stdin.readline().strip().split()))
g = [[] for x in range(n)]

for i in range(m):
    x, y = map(int, sys.stdin.readline().strip().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

if [] in g:
    print("No")
    exit(0)

ans = {0: -1}

while len(ans) < n:
    flag = False
    for k, v in list(ans.items()):
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                flag = True
    if flag == False:
        break

print("Yes")
for i in range(1, n):
    print(ans[i]+1)

### FIXED CODE ###


import sys, os, re
from pprint import pprint
from math import sin, cos, sqrt, radians

n, m = list(map(int, sys.stdin.readline().strip().split()))
g = [[] for x in range(n)]

for i in range(m):
    x, y = map(int, sys.stdin.readline().strip().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

if [] in g:
    print("No")
    exit(0)

ans = {0: -1}
tmp = [0]

while len(ans) < n:
    tmp_next = []
    for k in tmp:
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                tmp_next.append(node) 
                flag = True

        tmp = tmp_next
        if flag == False:
            break

    """
    flag = False    
    for k, v in list(ans.items()):
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                flag = True
    if flag == False:
        break
    """

print("Yes")
for i in range(1, n):
    print(ans[i]+1)
### BUGGY CODE ###

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

A, B = map(int, input().split())
if A > B:
    A, B = B, A
c = gcd(A, B)
li = [1]

for i in range(2, c+1):
    if i > c:
        break
    if c%i == 0:
        li.append(i)
        while c%i == 0:
            c = c//i

print(len(li))

### FIXED CODE ###

from math import sqrt, ceil

# ユークリッドの互除法で最大公約数を返す
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

A, B = map(int, input().split())
if A > B:
    A, B = B, A
g = gcd(A, B)
s = set(); s.add(1)
sqrt_g_plus = ceil(sqrt(g))+1
i = 2

# 最大公約数の平方根までの素数を見つける
while i < sqrt_g_plus:
    if g%i == 0:
        s.add(i)
        g //= i
    else:
        i += 1
# 平方根以上の素数がある場合、追加する（あるとした場合一つだけである）
if g > 1:
    s.add(g)

print(len(s))
### BUGGY CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
ans = 1000
purchase = 0

for i in range(1, N):
    tmp = ans
    
    if A[i] > A[i - 1]:
        while True:
            if tmp - A[i - 1] < 0:
                break
            tmp -= A[i - 1]
            purchase += 1
        ans = max(ans, tmp + A[i] * purchase)
        purchase = 0

print(ans)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
ans = 1000

for i in range(1, N):
    tmp = ans
    if A[i] > A[i - 1]:
        purchase = tmp // A[i - 1]
        ans = max(ans, tmp + (A[i] - A[i - 1]) * purchase)
        
print(ans)