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


num = 7
K = int(input())

flg_stop = False
count = 1

if K % 2 == 0:
    count = -1
    flg_stop = True


while not(flg_stop):
    mod_ = num % K
    if mod_ == 0:
        flg_stop = True
        continue
    num_2 = 7 * 10 ** count
    mod_2 = num_2 % K
    num = mod_ + mod_2
    count += 1

print(count)


### FIXED CODE ###

k = int(input())
i = 1
a = 7
a = a % k
while a != 0:
  i += 1
  a = (10*a + 7) % k
  if i == 10**6:
    i = -1
    break
 
print(i)
### BUGGY CODE ###

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():


    s = "#" + S()
    t = "#" + S()

    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]

    for i in range(len(t)-1):
        for j in range(len(s)-1):
            if t[i+1] == s[j+1]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])


    ans = ""
    now = dp[len(t)-1][len(s)-1]
    zahyo = [len(t)-1, len(s)-1]
    while now != 0:
        while dp[zahyo[0]][zahyo[1]-1]==now:
            zahyo[1]-=1
        while dp[zahyo[0]-1][zahyo[1]]==now:
            zahyo[0]-=1

        ans += t[zahyo[0]]

        now -= 1
        zahyo = [zahyo[0]-1, zahyo[1]-1]

    ans = ans[::-1]

    print(ans)

main()


### FIXED CODE ###

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():


    s = "#" + S()
    t = "#" + S()

    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]

    for i in range(len(t)-1):
        for j in range(len(s)-1):
            if t[i+1] == s[j+1]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])


    ans = ""
    now = dp[len(t)-1][len(s)-1]
    zahyo = [len(t)-1, len(s)-1]
    while now != 0:
        while dp[zahyo[0]][zahyo[1]-1]==now:
            zahyo[1]-=1
        while dp[zahyo[0]-1][zahyo[1]]==now:
            zahyo[0]-=1

        ans += t[zahyo[0]]

        now -= 1
        zahyo = [zahyo[0]-1, zahyo[1]-1]

    ans = ans[::-1]

    print(ans)

main()
### BUGGY CODE ###

N,M = list(map(int,input().split()))
LR = [list(map(int,input().split())) for i in range(M)]
elements = []
sets = {}

for i in range(M):
  ilist = []
  for j in range(LR[i][1]-LR[i][0]+1):
    ilist.append(LR[i][0]+j)
  elements.append(ilist)
  if i != 0:
    sets = sets & set(elements[i])
  else:
    sets = set(elements[i])

print(len(list(sets)))

### FIXED CODE ###

N, M = map(int,input().split())
L = []
R = []
for i in range(M):
  l, r = map(int,input().split())
  L.append(l)
  R.append(r)

max_l = max(L)
min_r = min(R)
print(max(min_r - max_l + 1, 0))
### BUGGY CODE ###

import collections

def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    sumA=sum(A)
    sumA2=(sumA+1)//2

    # dp[N][sum] : N個目までの合計がsumの数
    dp = [collections.defaultdict(int) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in dp[i].keys():
            if dp[i][j]==0:
                continue
            dp[i+1][j]+=dp[i][j]*2
            j2=min(sumA2,j+A[i])
            dp[i+1][j2]+=dp[i][j]
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        # dp[N][sum] : N個目までの合計がsumの数
        dp = [collections.defaultdict(int) for i in range(N+1)]
        dp[0][0]=1
        for i in range(N):
            for j in dp[i].keys():
                if dp[i][j]==0:
                    continue
                dp[i+1][j]+=dp[i][j]
                j2=min(sumA2+1,j+A[i])
                dp[i+1][j2]+=dp[i][j]
        ans=(ans+3*dp[N][sumA2])%mod

    return ans

print(solve())


### FIXED CODE ###

def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    sumA=sum(A)
    sumA2=(sumA+1)//2

    dp = [[0]*(sumA2+2) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(sumA2+1):
            if dp[i][j]!=0:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j]*2)%mod
                j2=min(sumA2,j+A[i])
                dp[i+1][j2]=(dp[i+1][j2]+dp[i][j])%mod
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        dp = [[0]*(sumA2+2) for i in range(N+1)]
        dp[0][0]=1
        for i in range(N):
            for j in range(sumA2+2):
                if dp[i][j]!=0:
                    dp[i+1][j]+=dp[i][j]
                    j2=min(sumA2+1,j+A[i])
                    dp[i+1][j2]+=dp[i][j]
        ans=(ans+3*dp[N][sumA2])%mod

    return ans

print(solve())
### BUGGY CODE ###

H,W=map(int,input().split())

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*10**7

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            MAP[i][j]="#"
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()  



### FIXED CODE ###

H,W=map(int,input().split())

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*(10**6+100)

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            MAP[i][j]="#"
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()
### BUGGY CODE ###

N = int(input())

target = dict()
for i in range(N):
	S = str(input())
	if S in target:
		count = target[S]
		target[S] += 1
	else: 
		target[S] = 1
ans = [k for k, v in target.items() if v == max(target.values())]
ans.sort()

for i in ans:
	print(i)

### FIXED CODE ###

N = int(input())

target = dict()
max_count = 0
max_key = list()
for i in range(N):
	S = str(input())
	if S in target:
		count = target[S] +1
		target[S] = count	
	else:
		target[S] = 1
		count = 1

	if max_count < count:
		max_count = count
		max_key = [S]
	elif max_count == count:
		max_key.append(S)

max_key.sort()
for i in max_key:
	print(i)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split()) 

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

factorial_map = {0: 1}
factorial_inv_map = {0: 1}
for i in range(1, r2 + c2 + 3):
  factorial_map[i] = (factorial_map[i - 1] * i) % MOD
  factorial_inv_map[i] = (factorial_inv_map[i - 1] * pow_mod(i, MOD - 2)) % MOD


a = 1
a *= factorial_map[r2 + c2 + 2]
a %= MOD
a *= factorial_inv_map[r2 + 1]
a %= MOD
a *= factorial_inv_map[c2 + 1]
a %= MOD

b = 1
b *= factorial_map[r2 + c1 + 1]
b %= MOD
b *= factorial_inv_map[r2 + 1]
b %= MOD
b *= factorial_inv_map[c1]
b %= MOD

c = 1
c *= factorial_map[r1 + c2 + 1]
c %= MOD
c *= factorial_inv_map[r1]
c %= MOD
c *= factorial_inv_map[c2 + 1]
c %= MOD

d = 1
d *= factorial_map[r1 + c1]
d %= MOD
d *= factorial_inv_map[r1]
d %= MOD
d *= factorial_inv_map[c1]
d %= MOD

ans = a
ans -= b
ans %= MOD
ans -= c 
ans %= MOD
ans += d
ans %= MOD

print(ans)

### FIXED CODE ###



def pow_mod(x, y):
    MOD = 1000000007
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

def main():
  MOD = 1000000007
  r1, c1, r2, c2 = map(int, input().split()) 

  points = {r2 + c2 + 2, r2 + 1, c2 + 1, r2 + c1 + 1, c1, r1 + c2 + 1, r1, r1 + c1}

  factorial_map = {0: 1}
  for i in range(1, r2 + c2 + 3):
    factorial_map[i] = (factorial_map[i - 1] * i) % MOD
    if i > 1 and (i - 2) not in points:
      del factorial_map[i-2]

  a = 1
  a *= factorial_map[r2 + c2 + 2]
  a %= MOD
  a *= pow_mod(factorial_map[r2 + 1], MOD - 2)
  a %= MOD
  a *= pow_mod(factorial_map[c2 + 1], MOD - 2)
  a %= MOD

  b = 1
  b *= factorial_map[r2 + c1 + 1]
  b %= MOD
  b *= pow_mod(factorial_map[r2 + 1], MOD - 2)
  b %= MOD
  b *= pow_mod(factorial_map[c1], MOD - 2)
  b %= MOD

  c = 1
  c *= factorial_map[r1 + c2 + 1]
  c %= MOD
  c *= pow_mod(factorial_map[r1], MOD - 2)
  c %= MOD
  c *= pow_mod(factorial_map[c2 + 1], MOD - 2)
  c %= MOD

  d = 1
  d *= factorial_map[r1 + c1]
  d %= MOD
  d *= pow_mod(factorial_map[r1], MOD - 2)
  d %= MOD
  d *= pow_mod(factorial_map[c1], MOD - 2)
  d %= MOD

  ans = a
  ans -= b
  ans %= MOD
  ans -= c 
  ans %= MOD
  ans += d
  ans %= MOD

  print(ans)


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

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
D = []
len = 0
for i in range(M):
    B,C = (int(i) for i in input().split())
    D.extend([C]*B)
    len += B
    cnt = min(N,len)
    D.sort(reverse = True)
    D = D[0:cnt]

for i in range(cnt):
    if A[0] < D[i]:
        heapq.heapreplace(A,D[i])
    else:
        break
print(sum(A))


### FIXED CODE ###

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
D = []
len = 0
BC = [0] * M

for i in range(M):
    BC[i] = list(map(int,input().split()))
BC.sort(key = lambda x:x[1],reverse = True)
for i in range(M):
    D.extend([BC[i][1]] * BC[i][0])
    len += BC[i][0]
    if len > N:
        break
cnt = min(N,len)
for i in range(cnt):
    if A[0] < D[i]:
        heapq.heapreplace(A,D[i])
    else:
        break
print(sum(A))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())

a,b=map(int,input().split())
A=[a]
B=[b]

l=[1 for i in range(N+1)]

L=[[]for i in range(N+1)]

for i in range(M-1):
    x,y=map(int,input().split())
    L[x].append(y)
    L[y].append(x)
    
l[a]=0
l[b]=0


P=a
for i in range(10**5):
    for j in L[P]:
        if l[j]==0:
            pass
        else:
            P=j
            l[j]=0
            A.append(j)
            break
    if len(L[P])==0:
        break
    elif max(L[P])==0:
        break
P=b
for i in range(10**5):
    for j in L[P]:
        if l[j]==0:
            pass
        else:
            P=j
            l[j]=0
            B.append(j)
            break
    if len(L[P])==0:
        break
    elif max(L[P])==0:
        break
A=A[::-1]
ans=A+B
print(len(ans))

ANS=str(ans[0])
for i in range(1,len(ans)):
    ANS+=" "+str(ans[i])
print(ANS)
        
    

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

R=[1 for i in range(N+1)]
A,B=map(int,input().split())
R[A]=0
R[B]=0

L=[[]for i in range(N+1)]
L[A].append(B)
L[B].append(A)

for i in range(M-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

l=[A]
P=A
#print(L)

for i in range(10**6):
    flag=0
    #print("P",L[P])
    for j in L[P]:
        #print("j",L,L[P],j,P)
        if R[j]==1:
            P=j
            R[j]=0
            l.append(j)
            flag+=1
            break
    if flag==0:
        break
#print(l)
r=[B]
P=B
for i in range(10**6):
    flag=0
    #print("P",L[P])
    for j in L[P]:
        #print("j",L,L[P],j,P)
        if R[j]==1:
            P=j
            R[j]=0
            r.append(j)
            flag+=1
            break
    if flag==0:
        break
#print(r)
l=l[::-1]
ans=l+r

ANS=str(ans[0])
for i in range(1,len(ans)):
    ANS+=" "+str(ans[i])
print(len(ans))
print(ANS)
### BUGGY CODE ###

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

dp = [-1] * (T + 3000)
dp[0] = 0
for a, b in sorted(AB):
    for i in range(T - 1, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i + a] < dp[i] + b:
            dp[i + a] = dp[i] + b
print(max(dp))


### FIXED CODE ###

def main():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for j in range(T - 1, -1, -1):
            if dp[j] == -1:
                continue
            if dp[j] + b > dp[j + a]:
                dp[j + a] = dp[j] + b
    print(max(dp))


main()
### BUGGY CODE ###

import numpy as np
import sys

X, Y, Z, K = map(int, input().split())
a = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')
b = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')
c = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')

amax = a.max()
bmax = b.max()
cmax = c.max()

a = amax - a
a.sort()
b = bmax - b
b.sort()
c = cmax - c
c.sort()


def func(o, p):
    min_ = 0
    max_ = o[-1] + p[-1]
    v = (min_ + max_) // 2
    while True:
        mat = np.searchsorted(o, v - p, side='right')
        sum_ = mat.sum()
        if sum_ > K:
            max_ = v - 1
            v = (v + min_) // 2
        elif sum_ == K:
            return v
        else:
            min_ = v + 1
            v = (v + max_ + 1) // 2


if X * Y > K:
    u = func(a, b)
    matr = np.searchsorted(a, u - b, side='right')
    d = np.array([],dtype='int64')
    for i in range(Y):
        d = np.append(d, a[:matr[i]] + b[i])
    d.sort()
else:
    d = (a + b.reshape([len(b), 1])).flatten()
    d.sort()

u = func(d, c)
matr = np.searchsorted(d, u - c, side='right')
e = np.array([],dtype='int64')
for i in range(Z):
    e = np.append(e, d[:matr[i]] + c[i])
e.sort()

t = amax + bmax + cmax
for ec in e:
    print(t - ec)

### FIXED CODE ###

import numpy as np
import sys

X, Y, Z, K = map(int, input().split())
a = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')
b = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')
c = np.array(list(map(int, sys.stdin.readline().split())), dtype='int64')

d = (a + b.reshape([len(b), 1])).flatten()
d.sort()
e = (d[-K:] + c.reshape([len(c), 1])).flatten()
e.sort()

for ec in e[-K:][::-1]:
    print(ec)
### BUGGY CODE ###

from heapq import heapify, heappush, heappop 

INF = 1001001001

N, Q = map(int, input().split())
STXs = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

#S-X, T-X, X
future_block = [(S - X, T - X, X) for S, T, X in STXs]
future_block.append((INF, INF, INF)) #sentinel
heapify(future_block)

#T-X, S-X, X
current_block = [(INF, INF, INF)] #sentinel
current_min_pair = (INF, INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[2] > x:
            current_min_pair = (t_x, s_x, x)
        heappush(current_block, (t_x, s_x, x))
    
    while current_block[0][0] <= D:
        if current_min_pair == heappop(current_block):
            current_min_pair = min(current_block, key = lambda t: t[2])

    print(-1 if current_min_pair[2] == INF else current_min_pair[2])


### FIXED CODE ###

from heapq import heapify, heappush, heappop 

INF = 1001001001

N, Q = map(int, input().split())
STXs = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

#S-X, T-X, X
future_block = [(S - X, T - X, X) for S, T, X in STXs]
future_block.append((INF, INF, INF)) #sentinel
heapify(future_block)

#T-X, X
current_block = [(INF, INF)] #sentinel
current_min_pair = (INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[1] > x:
            current_min_pair = (t_x, x)
        heappush(current_block, (t_x, x))
    
    search_min_flg = False
    while current_block[0][0] <= D:
        if current_min_pair == heappop(current_block):
            search_min_flg = True
    if search_min_flg:
        current_min_pair = min(current_block, key = lambda t: t[1])

    print(-1 if current_min_pair[1] == INF else current_min_pair[1])
### BUGGY CODE ###

from collections import defaultdict
def d():
    tree_map = defaultdict(list)
    value_map = defaultdict(int)
    N, Q = map(int,input().split())
    
    for _ in range(1, N):
        a, b = map(int,input().split())
        tree_map[a].append(b)
        tree_map[b].append(a)

    for _ in range(1, Q+1):
        p, x = map(int,input().split())
        value_map[p] += x

    res = [0] * N
    stack = []
    stack.append((1, 0))
    visited = set()
    while stack:
        i, s = stack.pop()
        visited.add(i)
        if value_map[i] != 0:
            s += value_map[i]
        res[i-1] += s
        
        for j in tree_map[i]:
            if j not in visited:
                stack.append((j, s))

    print(*res)


if __name__ == "__main__":
    d()

### FIXED CODE ###

from collections import defaultdict
def d():
    tree_map = defaultdict(list)
    value_map = defaultdict(int)
    N, Q = map(int,input().split())
    
    for _ in range(1, N):
        a, b = map(int,input().split())
        tree_map[a].append(b)
        tree_map[b].append(a)

    res = [0] * N

    for _ in range(1, Q+1):
        p, x = map(int,input().split())
        res[p-1] += x
    
    stack = []
    stack.append((1, -1, 0))

    while stack:
        i, p, s = stack.pop()

        res[i-1] += s
        s = res[i-1]
        
        for j in tree_map[i]:
            if j == p:
                continue
            else:
                stack.append((j, i, s))

    print(*res)


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

import sys
input = sys.stdin.readline

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

lst = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    L, R = map(int, input().split())
    for l in range(L + 1):
        lst[l][R] += 1

for l in range(N + 1):
    for r in range(N):
        lst[l][r + 1] += lst[l][r]

# for tmp in lst:
#     print (tmp)

for _ in range(Q):
    p, q = map(int, input().split())
    print (lst[p][q])

### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())

#input
lst = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    lst[R][L] += 1

lst = np.array(lst)
# print (lst)

#2次元累積和
for i in range(1, N + 1):
    lst[:,i] += lst[:, i - 1]
for j in range(1, N + 1):
    lst[j,:] += lst[j - 1, :]


#output
for _ in range(Q):
    p, q = map(int, input().split())
    print (lst[q, q] - lst[p-1, q] - lst[q, p-1] + lst[p-1, p-1])

# print (lst)
### BUGGY CODE ###

import sys
import itertools
from functools import reduce
from math import gcd

n = int(sys.stdin.read())
print(sum(reduce(gcd, abc) for abc in itertools.product(range(1, n + 1), repeat=3)))

### FIXED CODE ###

import sys
import itertools
from math import gcd

n = int(sys.stdin.read())
print(sum(gcd(gcd(abc[0], abc[1]), abc[2]) for abc in itertools.product(range(1, n + 1), repeat=3)))
### BUGGY CODE ###

import heapq
import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


for k in range(n):
	 for i in range(n):
		 for j in range(n):
			 road_matrix[i][j]  = min(road_matrix[i][k] + road_matrix[k][j], road_matrix[i][j])


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)
### BUGGY CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*n

    for i in range(n):
        if S[i:i+2] == 'AC':
            N[i] = 1
    for i in range(q):
        l,r = map(int,input().split())
        print(sum(N[l-1:r-1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*(n+1)

    for i in range(n):
        N[i+1] += N[i]
        if S[i:i+2] == 'AC':
            N[i+1] += 1
    for i in range(q):
        l,r = map(int,input().split())
        print(N[r-1]-N[l-1])


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

N = int(input())
list_card = list(map(int, input().split()))
count = 0
for x in set(list_card):
    count += list_card.count(x) - 1
print(N - (count + count%2))

### FIXED CODE ###

N = int(input())
list_card = list(map(int, input().split()))
##count = 0
##for x in set(list_card):
##    count += list_card.count(x) - 1
M = N - len(set(list_card))
print(N - (M + M%2))