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

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

#p[i色のスライム][j回まで色を変えられる]=色変えのコストを含まない最小コスト
p = [[0]*n for i in range(n)]
cnt = [[0]*n for i in range(n)]
#print(p)
for i in range(n):
  p[i][0]=a[i]
  for j in range(1,n):
    if i-j>=0:
      p[i][j]=min(a[i-j],p[i][j-1])
    elif i-j == -1:
      p[i][j]=min(a[n-1],p[i][j-1])
    else:  
      p[i][j]=min(a[n-(j-i)],p[i][j-1])
p = list(zip(*p))
ans = sum(p[0])
for i in range(1,n):
  ans = min(ans,sum(p[i])+x*i)
print(ans)

### FIXED CODE ###

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

#p[i色のスライム][j回まで色を変えられる]=色変えのコストを含まない最小コスト
p = [[0]*n for i in range(n)]

#print(p)
for i in range(n):
  p[i][0]=a[i]
  for j in range(1,n):
    if i-j>=0:
      p[i][j]=min(a[i-j],p[i][j-1])
    elif i-j == -1:
      p[i][j]=min(a[n-1],p[i][j-1])
    else:  
      p[i][j]=min(a[n-(j-i)],p[i][j-1])
p = list(zip(*p))
ans = sum(p[0])
for i in range(1,n):
  ans = min(ans,sum(p[i])+x*i)
print(ans)
### BUGGY CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    res = 0
for x in ls:
    res *= x
    if res > 10**18:
        res = -1
print(res)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

from collections import deque
import sys


N, D, A = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
M.sort()

q = deque()
qt = deque()

ans = 0
for x, h in M:
    if len(q) == 0:
        bomb = (h + A - 1) // A
        q.append((x + 2 * D, bomb))
        ans += bomb
    else:
        while h > 0:
            d, bomb = q.popleft()
            if x <= d:
                h -= bomb * A
                qt.append((d, bomb))
            if h > 0 and len(q) == 0:
                bomb = (h + A - 1) // A
                h -= bomb * A
                qt.append((x + 2 * D, bomb))
                ans += bomb
        while len(qt) > 0:
            q.appendleft(qt.pop())

print(ans)


### FIXED CODE ###

from collections import deque
import sys


N, D, A = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
M.sort()

q = deque()
qt = deque()

ans = 0
dmg = 0
for x, h in M:
    if len(q) == 0:
        bomb = (h + A - 1) // A
        q.append((x + 2 * D, bomb))
        dmg += bomb * A
        ans += bomb
    else:
        while len(q) > 0:
            d, bomb = q.popleft()
            if d < x:
                dmg -= bomb * A
            else:
                q.appendleft((d, bomb))
                break
        if h > dmg:
            bomb = ((h - dmg) + A - 1) // A
            q.append((x + 2 * D, bomb))
            dmg += bomb * A
            ans += bomb

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

import math

x = int(input())

div = []

i = 1
while i*i <= x:
    if x%i == 0:
        div.append(i)
        if i*i != x:
            div.append(x//i)
    i += 1

for d in div:

    minr = math.floor(math.sqrt(math.sqrt((x//d)/5)))
    if minr-d <= 0:
        minr = 0
    a = minr

    while (a-d)<=0 or 5*((a-d)**4) < x//d:
        a += 1
        b = a-d
        if a**5-b**5 == x:
            print(a, b)
            exit()
        if -a**5+b**5 == x:
            print(-a, -b)
            exit()

### FIXED CODE ###

import math

x = int(input())

a = 0
b = 0
while b**5 > -x:
    b -= 1

while a**5-b**5 != x:
    if a**5-b**5 < x:
        a += 1
    else:
        b += 1
        
print(a, b)
### BUGGY CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
for i in range(n):
  if arr[i] in s:
    continue
  for j in range(2,10**6//arr[i]+1):
    s.add(arr[i]*j)
ans=0
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    continue
  ans+=1
print(ans)

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    s.add(arr[i])
  for j in range(2,10**6//arr[i]+1):
    s.add(arr[i]*j)
ans=0
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    continue
  ans+=1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
*a, = sorted(map(int, input().split()), key=lambda x: -x)
for i in range(m):
    tmp = a.pop(0)
    tmp /= 2
    if len(a) == 0:
        a.append(tmp)
    for j in range(min(len(a), m-i)):
        if tmp > a[j]:
            a.insert(j, tmp)
            break
    else:
        a.append(tmp)

print(sum(map(int, a)))

### FIXED CODE ###

import heapq, math

n, m = map(int, input().split())
*a, = map(lambda x: -int(x), input().split())
heapq.heapify(a)

for i in range(m):
    tmp = heapq.heappop(a)
    tmp = math.ceil(tmp / 2)
    heapq.heappush(a, tmp)

print(-sum(a))
### BUGGY CODE ###

import numpy as np

n = int(input())
l = np.array(list(map(int, input().split())))

cnt = 0
for a in range(n):
    for b in range(a, n):
        for c in range(b, n):
            if a != b and b != c and c != a:
                if l[a] < (l[b] + l[c]) and l[b] < (l[a] + l[c]) and l[c] < (l[a] + l[b]):
                    cnt += 1

print(cnt)


### FIXED CODE ###

import numpy as np
import bisect

n = int(input())
l = np.array(list(map(int, input().split())))

# l.sort()

# ans = 0
# for a in range(n - 2):
#     for b in range(a + 1, n - 1):
#         ans += bisect.bisect_left(l, l[a] + l[b]) - (a + 1)
# print(ans)

res = 0
l = sorted(l)
for i in range(1, n - 1):
    b = l[i]
    for j in range(0, i):
        a = l[j]
        res += bisect.bisect_left(l, a + b) - (i + 1)
print(res)
### BUGGY CODE ###

N,M=map(int,input().split())
words=[[] for _ in range(N)]
for _ in range(M):
    p,S=input().split()
    p=int(p)-1
    words[p].append(S)
AC=0
WA=0
for a in words:
    for b in a:
        if a.count('WA') != 0 and len(a) == a.count('WA'):
            break
        if b=='AC':
            AC+=1
            break
        elif b=='WA':
            WA+=1
print(AC,WA)


### FIXED CODE ###

N,M=map(int,input().split())
words=[[] for _ in range(N)]
for _ in range(M):
    p,S=input().split()
    p=int(p)-1
    words[p].append(S)
AC=0
WA=0
for a in words:
    if a.count('WA') != 0 and len(a) == a.count('WA'):
        continue
    for b in a:
        if b=='AC':
            AC+=1
            break
        elif b=='WA':
            WA+=1
print(AC,WA)
### BUGGY CODE ###

h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i,j]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    ans=0
    for i in range(x,y-1,d):
        ans +=abs(adress[i+d][0]-adress[i][0])+abs(adress[i+d][1]-adress[i][1])
    print(ans)

### FIXED CODE ###

H, W, D = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
    l = map(int, input().split())
    for j, a in enumerate(l):
        m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
 
S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
    x, y = m[k]
    i, j = m[k - D]
    S[k] = S[k - D] + abs(x - i) + abs(y - j)
 
for l, r in LR:
    print(S[r] - S[l])
### BUGGY CODE ###

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

plus = []
minus = []

for i in a:
    minus.append(i-1)
    plus.append(i+1)

all_l = a + minus + plus
all_l.sort()
set_all = list(set(all_l))

ans = 0
for i in set_all:
    if all_l.count(i) > ans:
        ans = all_l.count(i)

print(ans)

### FIXED CODE ###

import collections

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

plus = []
minus = []

for i in a:
    minus.append(i-1)
    plus.append(i+1)

all_l = a + minus + plus
ans = collections.Counter(all_l)
print(ans.most_common(1)[0][1])
### BUGGY CODE ###

j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
exec("a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1;"*q)
print sum(c)-2

### FIXED CODE ###

j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
for p in[-1]*q:a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1
print sum(c)-2
### BUGGY CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

### FIXED CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)
### BUGGY CODE ###

n = int(input())

result = []

for i in input().split():
    result.append(i)
    result = result[::-1]

print(" ".join(result))

### FIXED CODE ###

from collections import deque

n = int(input())

result = deque()
index = 0

if n % 2 == 0:
    for i in input().split():
        if index % 2 == 1:
            result.appendleft(i)
            index += 1
        else:
            result.append(i)
            index += 1
else:
    for i in input().split():
        if index % 2 == 1:
            result.append(i)
            index += 1
        else:
            result.appendleft(i)
            index += 1

print(" ".join(result))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

d = []
for i in range(n):
    if a[i] in d:
        d.remove(a[i])
    else:
        d.append(a[i])
print(len(d))


### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter([int(input()) for _ in range(n)])

ans = 0
for key in a.keys():
    if a[key] % 2:
        ans += 1

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

import sys
S=sys.stdin.readline().strip()
if int(S)<=10**9:
    A=["0","0",S,"0","0","1"]
    print(" ".join(A))
else:
    for a in range(0,10**9):
        for b in range(0,10**9):
            for c in range(0,10**9):
                for d in range(0,10**9):
                    for e in range(0,10**9):
                        for f in range(0,10**9):
                            T=abs((c-a)*(f-b)-(d-b)*(e-a))
                            if S==T:
                                A=[str(a),str(b),str(c),str(d),str(e),str(f)]
                                print(" ".join(A))


### FIXED CODE ###

s=int(input());l=10**9;n=0--s//l;print(0,0,1,l,n,n*l-s)
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

from collections import Counter

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

c = Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

import bisect

A, B, Q = map(int, input().split())
ss = [int(input()) for _ in range(A)]
ts = [int(input()) for _ in range(B)]
xs = [int(input()) for _ in range(Q)]

ss.sort()
ts.sort()
for x in xs:
    i = bisect.bisect_left(ss, x)
    s1 = ss[i - 1] if 0 < i else -(10 ** 20)
    s2 = ss[i] if i < A else 10 ** 20
    i = bisect.bisect_left(ts, x)
    t1 = ts[i - 1] if 0 < i else -(10 ** 20)
    t2 = ts[i] if i < B else 10 ** 20

    # s1 < x < s2
    # t1 < x < t2
    print(min(
        x - min(s1, t1),  # s1, t1
        2 * (x - s1) + (t2 - x),  # s1, t2
        2 * (t2 - x) + (x - s1),  # t2, s1
        2 * (s2 - x) + (x - t1),  # s2, t1
        2 * (x - t1) + (s2 - x),  # t1, s2
        max(s2, t2) - x,  # s2, t2
    ))


### FIXED CODE ###

import bisect
import io
import sys

LINES = sys.stdin.read().splitlines()[::-1]


def readline():
    return LINES.pop()


A, B, Q = map(int, readline().split())
ss = [int(readline()) for _ in range(A)]
ts = [int(readline()) for _ in range(B)]
xs = [int(readline()) for _ in range(Q)]

ss.sort()
ts.sort()
for x in xs:
    i = bisect.bisect_left(ss, x)
    s1 = ss[i - 1] if 0 < i else -(10 ** 20)
    s2 = ss[i] if i < A else 10 ** 20
    i = bisect.bisect_left(ts, x)
    t1 = ts[i - 1] if 0 < i else -(10 ** 20)
    t2 = ts[i] if i < B else 10 ** 20

    # s1 < x < s2
    # t1 < x < t2
    print(min(
        x - min(s1, t1),  # s1, t1
        2 * (x - s1) + (t2 - x),  # s1, t2
        2 * (t2 - x) + (x - s1),  # t2, s1
        2 * (s2 - x) + (x - t1),  # s2, t1
        2 * (x - t1) + (s2 - x),  # t1, s2
        max(s2, t2) - x,  # s2, t2
    ))
### BUGGY CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1),k+1)
print (ans)

### FIXED CODE ###

import math
from functools import lru_cache

ls_gcd  = [[None for _ in range(201)] for _ in range(201)]
for i in range(201):
    for j in range(201):
        ls_gcd[i][j] = math.gcd(i,j)

# def gcd(a,b,c):
#     # ab = math.gcd(a,b)
#     # abc = math.gcd(ab,c)
#     ab = ls_gcd[a][b]
#     abc = ls_gcd[ab][c]
#     return abc

K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        ab = ls_gcd[i+1][j+1]
        t = ls_gcd[ab]
        for k in range(K):
            ans += t[k+1]
print (ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = [0]*(n+1)
x[0]=1
div = 1000000007

if not 1 in a:
    x[1]=1

for i in range(2,n+1):
    if not i in a:
        x[i] = (x[i-2] + x[i-1]) % div
print(x[n])

### FIXED CODE ###

def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = []
temp=0
for i in range(m):
    x.append(a[i]-temp-1)
    temp = a[i]+1
x.append(n-temp)

temp = 1
div = 1000000007

for i in x:
    temp = (temp*Fib(i+1))%div

print(temp)
### BUGGY CODE ###

n = int(input())
ans = [0] * n

for i in range(1, n):
    for j in range(1, n):
        for k in range(1, n):
            fn = i * i + j * j + k * k + i * j + j * k + k * i
            if fn > n:
                break
            ans[fn - 1] += 1

for i in range(n):
    print(ans[i])


### FIXED CODE ###

import math

n = int(input())
ans = [0] * n

for i in range(1, int(math.sqrt(n))):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            fn = i * i + j * j + k * k + i * j + j * k + k * i
            if fn > n:
                break
            if i != j and j != k and k != i:
                ans[fn - 1] += 6
            elif i == j and j == k:
                ans[fn - 1] += 1
            else:
                ans[fn - 1] += 3

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    d = [0]*((n+1)*(m+1))
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[(n+1)*(j+1)+i+1] = d[(n+1)*j+i]+1
            else:
                d[(n+1)*(j+1)+i+1] = max(d[(n+1)*j+i+1],d[(n+1)*(j+1)+i])
    print(d[-1])


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
### BUGGY CODE ###

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

def factorize(n: int) -> list:
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pairwize = True
alls = None
wize = None

for i in range(N):
    f = factorize(A[i])
    fs = set(f)
    # print(fs)

    if i == 0:
        wize = fs
        alls = fs
    else:
        if alls & fs:
            pairwize = False
        alls = alls | fs
        wize = wize & fs

if pairwize:
    print("pairwise coprime")
else:
    if wize:
        print("not coprime")
    else:
        print("setwise coprime")


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
max_A = 10**6+1

dp = [0] * (max_A)
for i in range(N):
    dp[A[i]] += 1

pairwise = True

for i in range(2, max_A):
    cnt = 0
    # 素数の倍数がdp配列に存在するか。自分以外にあれば2以上になる
    for j in range(i, max_A, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False

if pairwise:
    print("pairwise coprime")
    exit()

from math import gcd

g = 0
for i in range(N):
    g = gcd(g, A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

s = input()
dp = [[0]*(len(s)+1) for _ in range(2019)]
mod = 2019
num = 0
for i in s:
    num += 1
    for j in range(2019):
        dp[(j*10+int(i))%mod][num] = dp[j][num-1]
    dp[int(i)][num] += 1
    
print(sum(dp[0]))

### FIXED CODE ###

from collections import Counter
s = input()
a = [0]
mod = 2019
for i,j in enumerate(s[::-1]):
    a.append(a[-1]+int(j)*pow(10,i,mod))
    a[-1] %= mod
b = Counter(a)
ans = 0
for i in b.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###


    
def main():
    import sys
    sys.setrecursionlimit(10**6)
    def input(): return sys.stdin.readline().rstrip()

                
    def dfs(upper, lower, left, right):
        # 走査
        cntrow = [0]*(h)
        for i in range(upper, lower):
            for j in range(left, right):
                if g[i][j] == '#':
                    tmp = ans[i][j]
                    cntrow[i] += 1
        
        if sum(cntrow) == 1:
            for i in range(upper, lower):
                for j in range(left, right):
                    ans[i][j] = tmp
            return ans
        
        for i in range(upper, lower):
            if sum(cntrow[:i]) > 0 and sum(cntrow[i:]) > 0:
                dfs(upper, i, left, right)
                dfs(i, lower, left, right)
                break
        
        cnt = 0
        for i in range(upper, lower):
            if cntrow[i] > 1:
                tmp = i
                cnt += 1
        if cnt == 1:
            for j in range(left, right):
                if g[tmp][j] == '#':
                    dfs(upper, lower, left, j+1)
                    dfs(upper, lower, j+1, right)
                    break
        

    h, w, k = map(int, input().split())
    g = ['']*h
    ans = [[0]*w for _ in range(h)]
    cnt = 1
    for i in range(h):
        g[i] = input()
        for j in range(w):
            if g[i][j] == '#':
                ans[i][j] = cnt
                cnt += 1
    dfs(0, h, 0, w)
    for i in range(h):
        print(*ans[i])

        
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10**6)

    def input(): return sys.stdin.readline().rstrip()
        
    def dfs(upper, lower, left, right, cnt):
        
        if cnt == 1:
            ans[upper:lower, left:right] = np.max(ans[upper:lower, left:right])
            return

        elif cnt != max(cntrow[upper:lower]):
            for i in range(upper, lower):
                if cntrow[i]:
                    ncnt = sum(cntrow[upper:i+1])
                    dfs(upper, i+1, left, right, ncnt)
                    dfs(i+1, lower, left, right, cnt-ncnt)
                    break
            
        else:
            idx = cntrow[upper:lower].index(cnt)+upper
            for j in range(left, right):
                if g[idx][j] == '#':
                    dfs(upper, lower, left, j+1, 1)
                    cntrow[idx] -=1
                    dfs(upper, lower, j+1, right, cnt-1)
                    break

      
    h, w, k = map(int, input().split())
    g = ['']*h
    ans = np.zeros(shape=(h, w), dtype=int)
    cnt = 1
    cntrow = [0]*h
    for i in range(h):
        g[i] = input()
        for j in range(w):
            if g[i][j] == '#':
                ans[i, j] = cnt
                cntrow[i] += 1
                cnt += 1
    dfs(0, h, 0, w, k)
    for i in range(h):
        print(*ans[i])

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

K = int(input())
hist = set()

INF = 10**8

w = 0
for i in range(INF):
  w += 7 * pow(10,i,K)
  w %= K
  if w == 0:
    print(i+1)
    break
  else:
    if w in hist:
      print(-1)
      break
    else:
      hist.add(w)
      
#print(hist)


### FIXED CODE ###

K = int(input())
hist = set()

INF = 10**8

w = 0
for i in range(INF):
  w += 7 * pow(10,i,K)
  w %= K
  if w == 0:
    print(i+1)
    break
  else:
    if w in hist:
      print(-1)
      break
    else:
      hist.add(w)
      
#print(hist)
### BUGGY CODE ###

N = int(input())
List = list(map(int,input().split()))
List.sort()
Flags = [1]*N
counter = 0
for i in range(N):  
  flag = 0
  if i < N -1 and List[i] == List[i+1]:
    flag = 1
  if flag != 1 and Flags[i] != 0:
    counter += 1
  Flags = [0 if Flags[j]== 0 or List[j]%List[i]==0 else Flags[j] for j in range(N)]
print(counter)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
M = A[-1]+1
DP = [0]*M
for i in A:
  DP[i] += 1
  for j in range(i*2,M,i):
    DP[j] = 2
print(DP.count(1))
### BUGGY CODE ###

N,M=map(int,input().split())
XY=[[int(j)for j in input().split()]for _ in range(M)]
cnt=[1]*(N+1)
ans=[1]
for x,y in XY: 
  cnt[x]-=1
  cnt[y]+=1
  if x in ans and not y in ans: 
    ans.append(y)
  if x in ans and cnt[x]==0:
    ans.pop(ans.index(x))
print(len(ans))

### FIXED CODE ###

N,M=map(int,input().split())
XY=[[int(j)for j in input().split()]for _ in range(M)]
cnt=[1]*(N+1)
ans=[False]*(N+1)
ans[1]=True
for x,y in XY: 
  cnt[x]-=1
  cnt[y]+=1
  if ans[x] and not ans[y]: 
    ans[y]=True
  if ans[x] and cnt[x]==0:
    ans[x]=False
print(sum(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

    if i > 0: res += rec(i-1,j,k)*i
    if j > 0: res += rec(i+1,j-1,k)*j
    if k > 0: res += rec(i,j+1,k-1)*k
    res += N
    res *= 1.0/(i+j+k)
    dp[i][j][k] = res
    return res

one = a.count(1)
two = a.count(2)
three = a.count(3)

#print(dp)
print(rec(one,two,three))
#print(dp)


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K



dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])