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

# K = 37564
# S = "whydidyoudesertme"
# K = 5
# S = "oof"
K = int(input())
S = input()

P = 10 ** 9 + 7
N = len(S)

P25 = [1] * (K + 1)
P26 = [1] * (K + 1)
F = [1] * (N + K)
INV = [1] * (N + K)
INVF = [1] * (N + K)

p25 = 1
p26 = 1
for i in range(1, K + 1):
    p25 *= 25
    p25 %= P
    P25[i] = p25

    p26 *= 26
    p26 %= P
    P26[i] = p26

f = 1
invf = 1
for i in range(2, N + K):
    f *= i
    f %= P
    F[i] = f

    INV[i] = P - INV[P % i] * (P // i) % P
    invf *= INV[i]
    invf %= P
    INVF[i] = invf


def comb_rep(n, r):
    return F[n + r - 1] * INVF[r] * INVF[n - 1]


ret = 0
for i in range(K + 1):
    ret += (
        P25[i] *
        P26[K - i] *
        comb_rep(N, i)
    )
print(ret % P)


### FIXED CODE ###

#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys


def main(K, N):
    P = 10 ** 9 + 7

    P25 = [1] * (K + 1)
    P26 = [1] * (K + 1)
    F = [1] * (N + K)
    INV = [1] * (N + K)
    INVF = [1] * (N + K)

    p25 = 1
    p26 = 1
    for i in range(1, K + 1):
        p25 *= 25
        p25 %= P
        P25[i] = p25

        p26 *= 26
        p26 %= P
        P26[i] = p26

    f = 1
    invf = 1
    for i in range(2, N + K):
        f *= i
        f %= P
        F[i] = f
        q, r = divmod(P, i)
        INV[i] = -INV[r] * q % P
        invf *= INV[i]
        invf %= P
        INVF[i] = invf

    def comb_rep(n, r):
        return (F[n + r - 1] * INVF[r] % P) * INVF[n - 1] % P

    ret = 0
    for i in range(K + 1):
        ret += (
            P25[i] *
            P26[K - i] % P *
            comb_rep(N, i) % P
        )
    return (ret % P)


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8)')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    # read parameter
    from my_module import main
    K = int(input())
    S = input()
    print(main(K, len(S)))
### BUGGY CODE ###

from math import gcd
N=int(input())
A=list(map(int, input().split()))


A=sorted(A)
gcda=A[0]
gcdais=True
gcdb=A[0]
MAX=max(A)
counts=[0]*MAX
counts[A[0]-1]+=1
for i in range(1,N):
    
    a=A[i]
    gcdb=gcd(gcdb, a)
    counts[a-1]+=1

for i in range(1,MAX):
    count=0
    now=i+1
    while now<=MAX:
        if counts[now-1]!=0:
            count+=counts[now-1]
        now+=(i+1)
    if count>=2:
        gcdais=False
    #print(count)
    
#print(counts)
if gcdais:
    print("pairwise coprime")
elif gcdb==1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###


from math import gcd
N=int(input())
A=list(map(int, input().split()))


A=sorted(A)
gcda=A[0]
gcdais=True
gcdb=A[0]
MAX=max(A)
counts=[0]*MAX
counts[A[0]-1]+=1
for i in range(1,N):
    
    a=A[i]
    gcdb=gcd(gcdb, a)
    counts[a-1]+=1

for i in range(1,MAX):
    count=0
    now=i+1
    while now<=MAX:
        if counts[now-1]!=0:
            count+=counts[now-1]
        now+=(i+1)
    if count>=2:
        gcdais=False
    #print(count)
    
#print(counts)
if gcdais:
    print("pairwise coprime")
elif gcdb==1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import sys
h, w = map(int, input().split())
print(h, w)
while h != 0:
    for _ in range(h):
        for _ in range(w):
            sys.stdout.write("#")
        print()
h, w = map(int, input().split())


### FIXED CODE ###

import sys
h, w = map(int, input().split())
while h != 0:
    for _ in range(h):
        for _ in range(w):
            sys.stdout.write("#")
        print()
    print()
    h, w = map(int, input().split())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 14:22:54 2020

@author: Maruthi Srinivas
"""
import sys
sys.setrecursionlimit(10000000)
def dfs(node,graph):
    temp=0
    for i in graph[node]:
        temp=max(temp,dfs(i,graph)+1)
    return temp
            
v,e=map(int,input().split())
adj={x:[] for x in range(v+1)}
for i in range(e):
    x,y=map(int,input().split())
    adj[x].append(y)
m=-1
for i in range(1,v+1):
    visited=[False]*(v+1)
    x=dfs(i,adj)
    m=max(m,x)
print(m)



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 14:22:54 2020

@author: Maruthi Srinivas
"""
import sys
sys.setrecursionlimit(1000000)
def dfs(node,graph,dp):
    temp=0
    if dp[node]!=-1:
        return dp[node]
    for i in graph[node]:
        temp=max(temp,dfs(i,graph,dp)+1)
    dp[node]=temp
    return temp
            
v,e=map(int,input().split())
adj={x:[] for x in range(v+1)}
for i in range(e):
    x,y=map(int,input().split())
    adj[x].append(y)
m=-1
dp=[-1]*(v+1)
for i in range(1,v+1):
    x=dfs(i,adj,dp)
    m=max(m,x)
print(m)
### BUGGY CODE ###

import itertools

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

for v in itertools.combinations(p, K):
    if ans > sum(v):
        ans = sum(v)

print(ans)


### FIXED CODE ###

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

ans=0
p.sort()
for i in range(K):
    ans += p[i]
print(ans)
### BUGGY CODE ###

import numpy as np
from copy import deepcopy
import sys
input = sys.stdin.readline

def draft(A, K, N):
    A = np.array(A)
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N+1, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        A = np.cumsum(tmp)[:-1]
    for i in range(N):
        print(int(A[i]), end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

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

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        val[0] += 1
        for i in range(N):
            cur = int(S[N - i - 1 :]) % P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


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

import collections
N = int(input())
l = list(map(int,input().split()))
c = collections.Counter(l)
li = []
for k,v in c.items():
    li.append(v*(v-1)//2)
    
for i in range(N):
  s = sum(li) - c[l[i]] + 1
  print(s)


### FIXED CODE ###

import collections
N = int(input())
l = list(map(int,input().split()))
c = collections.Counter(l)
cnt = 0
for v in c.values():
    cnt += v*(v-1)//2
    
for i in range(N):
  print(cnt - c[l[i]] + 1)
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]

def bfs(l):
    ans = 0
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    ans = max(ans,check[ny][nx])
                    q.append([ny,nx])
    return ans 

L = []
for h,a in enumerate(A):
    for w,a_ in enumerate(a):
        if a_ == '#':
            L.append([h,w])
print(bfs(L))

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]

def bfs(l):
    ans = 0
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    ans = max(ans,check[ny][nx])
                    q.append([ny,nx])
    return ans 

L = []
for h,a in enumerate(A):
    for w,a_ in enumerate(a):
        if a_ == '#':
            L.append([h,w])
print(bfs(L))
### BUGGY CODE ###

def main():
    N = int(input())
    pts = []
    while N != 0:
        x, y = map(int, input().split())
        pts+= [[x,y]]
        N = N - 1

    m = 0
    for i in range(0,len(pts)):
        for j in range(0,i):
            m = max(m, abs(pts[i][0]-pts[j][0]) + abs(pts[i][1] - pts[j][1]))
    print(m)

main()


### FIXED CODE ###

def main():
    N = int(input())
    x, y = map(int, input().split())
    a1 = x + y
    a2 = x + y
    b1 = y - x
    b2 = y - x
    N -= 1
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
px = py = pz = 0
for a in A:
  if a == 1:
    px += 1
  elif a == 2:
    py += 1
  elif a == 3:
    pz += 1

K = sum(A)

is_not_added = [[[True]*(N+1) for y in range(N+1)] for x in range(N+1)]
xyz = [[[0, 0, 0]]]
is_not_added[0][0][0] = False

transition = [[1, 0, 0, 0], [-1, 1, 0, 1], [0, -1, 1, 2]]
for k in range(1, K+1):
  _xyz = []
  for x, y, z in xyz[k-1]:
    for dx, dy, dz, _ in transition:
      if 0<=x+dx<=N and 0<=y+dy<=N and 0<=z+dz<=N \
          and is_not_added[x+dx][y+dy][z+dz]:
        is_not_added[x+dx][y+dy][z+dz] = False
        _xyz.append([x+dx, y+dy, z+dz])
  
  xyz.append(_xyz)


dp = [[[0]*(N+1) for y in range(N+1)] for x in range(N+1)]
for k in range(1, K+1):
  for x, y, z in xyz[k]:
    for dx, dy, dz, idx in transition:
      if 0<=x-dx<=N and 0<=y-dy<=N and 0<=z-dz<=N:
        w = [x, y, z][idx]
        s = x + y + z
        dp[x][y][z] += (dp[x-dx][y-dy][z-dz] + N/s) * w/s

print(dp[px][py][pz])

### FIXED CODE ###

N = int(input())
A = input().split()
px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nx+1) for y in range(ny+1)] for z in range(nz+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[z][y][x-1]*x/s
        if y > 0:
          t += dp[z][y-1][x+1]*y/s
        if z > 0:
          t += dp[z-1][y+1][x]*z/s
        
        dp[z][y][x] += t


print(dp[pz][py][px])
### BUGGY CODE ###

from fractions import gcd
a,b = map(int, input().split())
ans = 1
count = 2
num=gcd(a,b)

if a==1 or b==1:
    print(1)
else:
    while num!=1:
        if num%count==0:
            ans+=1
            while num%count==0:
                num= num/count
            count+=1
        else:
            count+=1
    print(ans)


### FIXED CODE ###

from fractions import gcd
a,b = map(int, input().split())
# ans = 1
count = 2
n=gcd(a,b)

ans = set([1])
while n % 2 == 0:
    ans.add(2)
    n //= 2
f = 3
while f * f <= n:
    if n % f == 0:
        ans.add(f)
        n //= f
    else:
        f += 2
if n != 1:
    ans.add(n)
print(len(ans))
### BUGGY CODE ###


import math

def read_input():
    n = int(input())
    return n


def submit():
    n = read_input()

    factor_cand = int(math.ceil(math.sqrt(n)))

    while n % factor_cand:
        factor_cand += 1

    a = int(n / factor_cand)
    b = int(factor_cand)

    al = len([c for c in str(a)])
    bl = len([c for c in str(b)])

    print(max(al, bl))



if __name__ == '__main__':
    submit()


### FIXED CODE ###


import math

def read_input():
    n = int(input())
    return n


def submit():
    n = read_input()

    factor_cand = int(math.ceil(math.sqrt(n)))

    while n % factor_cand:
        factor_cand -= 1

        if factor_cand == 1:
            nl = len([c for c in str(n)])
            print(nl)
            return

    a = int(n / factor_cand)
    b = int(factor_cand)

    al = len([c for c in str(a)])
    bl = len([c for c in str(b)])

    print(max(al, bl))



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

n = int(input())
ans = 0

for i in range(n + 1):
    if "3" in str(i) and "5" in str(i) and "7" in str(i):
        flag = True
        for j in str(i):
            if j != '3' and j != '5' and j != '7':
                flag = False
                break
        if flag:
            ans += 1

print(ans)

### FIXED CODE ###

import itertools as it

n = input()
ans = 0
nums = ['3', '7', '5']

for j in range(1, len(n) + 1):
    for i in it.product(nums, repeat=j):
        if int(n) >= int("".join(i)) and '3' in i and '5' in i and '7' in i:
            ans += 1

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

mod = 10**9+7
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)

if len(a) != len(set(a)) or len(b) != len(set(b)):
    print(0)
    exit()

#a = set(a)
#b = set(b)

c = 1
N = 0
M = 0
for k in range(n*m, 0, -1):
    if k in a and k in b:
        N += 1
        M += 1
    elif k in a:
        c *= M
        N += 1
    elif k in b:
        c *= N
        M += 1
    else:
        c *= M*N - (m*n-k)
    c %= mod

print(c)


### FIXED CODE ###

mod = 10**9+7
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)

if len(a) != len(set(a)) or len(b) != len(set(b)):
    print(0)
    exit()

a = set(a)
b = set(b)

c = 1
N = 0
M = 0
for k in range(n*m, 0, -1):
    if k in a and k in b:
        N += 1
        M += 1
    elif k in a:
        c *= M
        N += 1
    elif k in b:
        c *= N
        M += 1
    else:
        c *= M*N - (m*n-k)
    c %= mod

print(c)
### BUGGY CODE ###

k = int(input())

d = [[] for _ in range(k)]
for i in range(1, k+1):
    for ii in range(1, k+1):
        if i % ii == 0:
            d[i-1].append(ii)

ans = 0
for a1 in range(k):
    for a2 in range(k):
        for a3 in range(k):
            ans += max(set(d[a1]) & set(d[a2]) & set(d[a3]))

print(ans)

### FIXED CODE ###

import itertools
k = int(input())

d = [[] for _ in range(k)]

for i in range(1, k+1):
    n = 1
    while i*n <= k:
        d[i*n-1].append(i)
        n += 1

seq = [i for i in range(1, k+1)]
ans = 0
A = list(itertools.combinations_with_replacement(seq, 3))
for a in A:
    a1 = a[0]
    a2 = a[1]
    a3 = a[2]
    if a1 == a2 == a3:
        m = 1
    elif a1 == a2 or a1 == a3 or a2 == a3:
        m = 3
    else:
        m = 6
    ans += max(set(d[a1-1]) & set(d[a2-1]) & set(d[a3-1])) * m

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

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    hl=list(map(int,input().split()))
    cntmax=0
    #スタート位置
    for i in range(n):
        #右に移動
        cnt = 0
        for j in range(i,n-1):
            if hl[j] >= hl[j+1]:
                cnt+=1
                if cnt==n-1-i:
                    cntmax=max(cnt,cntmax)
            else:
                cntmax=max(cnt,cntmax)
                break
    print(cntmax)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    cnt=0
    cntmax=0
    for i in range(n-1):
        if l[i]>=l[i+1]:
            cnt+=1
            cntmax=max(cnt,cntmax)
        else:
            cntmax=max(cnt,cntmax)
            cnt=0
    print(cntmax)
resolve()
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array([int(i) for i in input().split()])
P = []
for i in range(N):
    if i == N - 1:
        P.append([0.5] + [0] * (N - 2) + [0.5])
    else:
        P.append([0] * i + [0.5, 0.5] + [0] * (N - 2 - i))
P = np.array(P)
for i in np.dot(np.linalg.inv(P), A):
    print(int(i)," ", end="")


### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array([int(i) for i in input().split()])
# dif = A1-A2+A3-A4 ...
dif = sum([A[i] * pow(-1, i) for i in range(N - 1)])
ans = [0] * N
ans[0] = A[-1] + dif
ans[-1] = A[-1] - dif
for i in range(1, N - 1):
    ans[i] = 2 * A[i - 1] - ans[i - 1]
print(*ans)
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        if i != 0:
            for l in range(ma):
                if DP[i-1][j][l]:
                    DP[i][j][abs(l-k)] = 1
                    DP[i][j][l+k] = 1
        if j != 0:
            for l in range(ma):
                if DP[i][j-1][l]:
                    DP[i][j][abs(l-k)] = 1
                    DP[i][j][l+k] = 1

for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()



### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s):
    global ans
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t)


ans = [None] * N
dist = [0] * N
s = dfs1(0)
dfs2(s)

for x in ans:
    print(x)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)
### BUGGY CODE ###

import sys
from collections import Counter
from operator import mul
from functools import reduce
readline = sys.stdin.readline

#エラトステネスの篩と素因数分解

M = 10**6 + 3
prime = [0]*M
for i in range(2, M):
    if prime[i]:
        continue
    for j in range(i, M, i):
        if not prime[j]:
            prime[j] = i

def pd(x):
    C = Counter()
    while x > 1:
        C[prime[x]] += 1
        x //= prime[x]
    return C

MOD = 998244353
N = int(readline())
A = list(map(int, readline().split()))
C = Counter(A)
mA = max(A) + 1
table = [0]*mA
table2 = [0]*mA
T = [0]*mA
i2 = pow(2, MOD-2, MOD)

for k in A:
    pk = pd(k)
    lk = list(pk.keys())
    lv = [v+1 for v in pk.values()]
    ll = len(pk)
    for s in range(reduce(mul, lv, 1)):
        res = 1
        for idx in range(ll):
            res *= pow(lk[idx], s%lv[idx])
            s //= lv[idx]
        table[res] += k
        table2[res] += k*k

T = [(x1*x1-x2)*i2%MOD for x1, x2 in zip(table, table2)]

ans = 0
coeff = [0]*mA
for i in range(1, mA):
    
    k = T[i]
    l = - coeff[i] + pow(i, MOD-2, MOD)
    ans = (ans+l*k)%MOD
    for j in range(2*i, mA, i):
        coeff[j] = (coeff[j] + l)%MOD
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline    
MOD = 998244353
N = int(readline())
A = list(map(int, readline().split()))
mA = max(A) + 1
T = [0]*mA
i2 = pow(2, MOD-2, MOD)


table = [0]*mA
table2 = [0]*mA
for a in A:
    table[a] = (table[a] + a)%MOD
    table2[a] = (table2[a] + a*a)%MOD
prime = [True]*mA
for p in range(2, mA):
    if not prime[p]:
        continue
    for k in range((mA-1)//p, 0, -1):
        table[k] = (table[k] + table[k*p])%MOD
        table2[k] = (table2[k] + table2[k*p])%MOD
        prime[k*p] = False

T = [(x1*x1-x2)*i2%MOD for x1, x2 in zip(table, table2)]

ans = 0
coeff = [0]*mA
for i in range(1, mA):
    k = T[i]
    l = - coeff[i] + pow(i, MOD-2, MOD)
    ans = (ans+l*k)%MOD
    for j in range(2*i, mA, i):
        coeff[j] = (coeff[j] + l)%MOD
print(ans)
### BUGGY CODE ###

n = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in a:
  l = list(map(lambda x: i % x, a))
  # print(l)
  if l.count(0) == 1:
    count += 1
print(count)

### FIXED CODE ###

def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]
  tf=[True]*maxa
  r=0
  n-=1
  for i in range(n): # maxa以外の処理
    a_i=a[i]
    if tf[a_i-1] ==True: # これまでに素の場合のみ処理実行
      for j in range(a_i - 1,maxa,a_i):
        tf[j]=False
      if a_i < a[i+1]: # a[i]とa[i+1]が同値の場合を排除
        r+=1
  if tf[-1] == True: # maxaへの処理
     r+=1
  print(r)
main()