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

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    node_unused_color = [{i for i in range(max_root)} for j in range(n)]

    que = queue.Queue()
    que.put(0)

    while que.qsize() > 0:
        node = que.get()
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            chosen_color = -1
            for tmp_a in node_unused_color[ai]:
                if tmp_a in node_unused_color[bi]:
                    chosen_color = tmp_a
                    break
            node_unused_color[ai] -= {chosen_color}
            node_unused_color[bi] -= {chosen_color}
            edge_dic[(ai, bi)] = chosen_color
            que.put(k)

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    que = queue.Queue()
    que.put((0, -1))

    while que.qsize() > 0:
        node, used_color = que.get()
        current_color = 0 if used_color != 0 else 1
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            edge_dic[(ai, bi)] = current_color
            que.put((k, current_color))
            current_color = current_color + 1 if used_color != current_color + 1 else current_color + 2

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


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

from collections import Counter

s = input()
n = len(s)

T = [0] * (n + 1)

for k in range(n):
	tmp = int(s[k:])
	T[k] = tmp % 2019
    
c = Counter(T)

cnt = 0
for v in c.values():
	if v > 1:
		cnt += v * (v - 1) // 2

print(cnt)

### FIXED CODE ###

s = input()
n = len(s)

MOD = 2019
T = [1] + [0] * 2018
d, p = 0, 1
for c in reversed(s):
	d = (d + p * int(c)) % MOD
	p = p * 10 % 2019
	T[d] += 1

print(sum(x * (x - 1) // 2 for x in T))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    flg = 0
    for i in range(N):
        if flg!=0:
            if i==flg:
                flg=0
            else:
                continue
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                flg=j+1
                break
        if cnt < tmp:
            cnt=tmp
        if cnt >= N-1:
            print(cnt)
            return
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    flg = 0
    for i in range(N):
        if cnt >= N-i:
            print(cnt)
            return
        if flg!=0:
            if i==flg:
                flg=0
            else:
                continue
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                flg=j+1
                if cnt >= N-j+1:
                    print(cnt)
                    return
                break
        if cnt < tmp:
            cnt=tmp
    print(cnt)


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

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    a[n-1] //= 2
print(sum(a))

### FIXED CODE ###

import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))
### BUGGY CODE ###

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

from collections import Counter
c = Counter(a)

for i in range(n):
   c[a[i]] -= 1
   tmp = [x*(x-1)//2 for x in c.values()]
   print(sum(tmp))
   c[a[i]] += 1


### FIXED CODE ###

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

from collections import Counter
c = Counter(a)
combi = {}
for k, v in c.items():
   combi[k] = v*(v-1)//2
sumc = sum(list(combi.values()))

for i in range(n):
   x = c[a[i]] - 1
   ans = sumc - combi[a[i]] + x*(x-1)//2
   print(ans)
### BUGGY CODE ###

from sys import setrecursionlimit

def f(u, l, r):
    if l > r:
        return (0, 0)
    if dp[l][r] is not None:
        return dp[l][r]
    t0 = None
    x, y = f(u ^ 1, l + 1, r)
    if u == 0:
        t0 = (x + a[l], y)
    else:
        t0 = (x, y + a[l])
    t1 = None
    x, y = f(u ^ 1, l, r - 1)
    if u == 0:
        t1 = (x + a[r], y)
    else:
        t1 = (x, y + a[r])
    if t0 is None:
        result = t1
    elif t1 is None:
        result = t0
    else:
        if t0[u] - t0[u ^ 1] > t1[u] - t1[u ^ 1]:
            result = t0
        else:
            result = t1
    dp[l][r] = result
    return result

setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
t = f(0, 0, N - 1)
print(t[0] - t[1])


### FIXED CODE ###

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

dp = [[0] * (N + 1) for _ in range(N + 1)]
for l in range(1, N + 1):
  for i in range(N + 1 - l):
    j = i + l
    if (N - l) % 2 == 0:
      dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
    else:
      dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
print(dp[0][N])
### BUGGY CODE ###

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

i=0
while i<len(S)-1:
    if S[i]!='a' and 123-ord(S[i])<=N:
        N-=123-ord(S[i])
        S[i]='a'
    i+=1

while N:
    if S[-1]=='z':
        S[-1]='a'
    else:
        S[-1]=chr(ord(S[-1])+1)
    N-=1

print(''.join(S))


### FIXED CODE ###

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

i=0
while i<len(S)-1:
    if S[i]!='a' and 123-ord(S[i])<=N:
        N-=123-ord(S[i])
        S[i]='a'
    i+=1

N=N%26
while N:
    if S[-1]=='z':
        S[-1]='a'
    else:
        S[-1]=chr(ord(S[-1])+1)
    N-=1

print(''.join(S))
### BUGGY CODE ###

from operator import mul
from functools import reduce

count = int(input())
list = [int(x) for x in input().split()]

a = reduce(mul, list)

if a > 1000000000000000000:
    print('-1')
else:
    print(a)

### FIXED CODE ###

def main ():
  count = int(input())
  c = list(map(int,input().split()))

  if 0 in c:
    print(0)
    return

  result = 1
  for a in c:
    result *= a
    if result > 1000000000000000000:
      print(-1)
      return

  print(result)

main()
### BUGGY CODE ###

n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 61
b  = 1

for i in range(0, 61):
	c = 0
	
	for x in xs:
		if (x & b) != 0:
			c += 1
	
	bs[i] = c
	b   <<= 1

b = 1
r = 0

for i in range(0, 61):
	if 0 < bs[i] and bs[i] < n:
		r += ((n - bs[i]) * bs[i]) * b
		
	b <<= 1
	
print(r % m)


### FIXED CODE ###

n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 60
b  = 1

for x in xs:
	e = 0
	
	while 0 < x:
		if x % 2 == 1:
			bs[e] += 1
			
		e  += 1
		x //= 2

b = 1
r = 0

for i in range(0, 60):
	r  += ((n - bs[i]) * bs[i]) * b
	b <<= 1
	
print(r % m)
### BUGGY CODE ###

N, W = map(int, input().split())
l = []
for i in range(N):
  L = list(map(int, input().split()))
  l.append(L)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j >= l[i-1][0]:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
l = []
for i in range(N):
  L = list(map(int, input().split()))
  l.append(L)
sum_of_weight = 0
sum_of_value = 0
for i in range(N):
  sum_of_weight += l[i][0]
  sum_of_value += l[i][1]
dp = [[sum_of_weight+1 for i in range(sum_of_value+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for j in range(sum_of_value+1):
    if j >= l[i-1][1]:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-l[i-1][1]]+l[i-1][0])
    else:
      dp[i][j] = dp[i-1][j]
ans = 0
for i in range(N+1):
  for j in range(sum_of_value+1):
    if W >= dp[i][j] and ans < j:
      ans = j
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split(" "))
A, B, C = [list(map(int, input().split(" "))) for _ in range(3)]
# X, Y, Z, K = 1000, 1000, 1000, 3000
# A, B, C = [[i*j for j in range(1000)] for i in range(3)]

ab_cakes = []
for a in A:
    for b in B:
        ab_cakes.append(a+b)

ab_cakes = sorted(ab_cakes, reverse=True)[:K]

abc_cakes = []
for ab in ab_cakes:
    for c in C:
        abc_cakes.append(ab + c)

abc_cakes = sorted(abc_cakes, reverse=True)[:K]

for abc in abc_cakes:
    print(abc)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split(" "))
A, B, C = [list(map(int, input().split(" "))) for _ in range(3)]
# X, Y, Z, K = 1000, 1000, 1000, 3000
# A, B, C = [[i*j for j in range(1000)] for i in range(3)]

ab_cakes = []
for a in A:
    for b in B:
        ab_cakes.append(a+b)

ab_cakes = sorted(ab_cakes, reverse=True)[:K]

abc_cakes = []
for ab in ab_cakes:
    for c in C:
        abc_cakes.append(ab + c)

abc_cakes = sorted(abc_cakes, reverse=True)[:K]

for abc in abc_cakes:
    print(abc)
### BUGGY CODE ###

import math
import copy

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()

q = int(input())
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

ALL = [i + 1 for i in range(10**5)]
ALL2 = copy.deepcopy(ALL)

for i in range(q):
    ALL = ALL2[s[i][0] - 1:s[i][1]]
    length = len(set(ALL) & set(W))
    print(length)
    ALL = ALL2

### FIXED CODE ###

import math
import copy

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()
W.append(10**5)
q = int(input())
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

j = 0
Z = []
for i in range(10 ** 5):
    if i < W[j]:
        Z.append(j)
    else:
        j += 1
        Z.append(j)

for i in range(q):
    if Z[s[i][0]] != Z[s[i][0] - 1]:
        print(Z[s[i][1]] - Z[s[i][0]] + 1)
    else:
        print(Z[s[i][1]] - Z[s[i][0]])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate


N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
info = [list(map(int,input().split())) for _ in range(M)]

info = sorted(info, key=lambda x:-x[1])

def calc(num):
    res = 0
    for i in range(M):
        B,C = info[i]
        if B <= num:
            res += B*C
            num -= B
        else:
            res += C*num
            num = 0
    return res

cs = [0] + list(accumulate(A))
ans = 0
# i:いくつ変換するか
for i in range(N+1):
    res = cs[N] - cs[i] + calc(i)
    ans = max(ans,res)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate


N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
info = [list(map(int,input().split())) for _ in range(M)]

info = sorted(info, key=lambda x:-x[1])

calc = [0]
for B, C in info:
    if len(calc) + B <= N+1:
        calc +=[C]*B
    else:
        calc += [C]*(N+1-len(calc))

calc += [0]*(N+1-len(calc))
calc = list(accumulate(calc))

cs = [0] + list(accumulate(A))
ans = 0
# i:いくつ変換するか
for i in range(N+1):
    res = cs[N] - cs[i] + calc[i]
    ans = max(ans,res)

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

from sys import stdin
import numpy as np

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans+=np.gcd(i,np.gcd(j,k))
print(str(ans)+"\n")

### FIXED CODE ###

from sys import stdin

def gcd(a,b):
    if a<b:
        tmp=a
        a=b
        b=tmp
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans+=gcd(i,gcd(j,k))
print(str(ans)+"\n")
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline

h, w = map(int, input().split())
# 蛮兵
painted = [['#'] * (w + 2)]
painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
painted.append(['#'] * (w + 2))

que = deque()

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if painted[y][x] == '#':
            painted[y][x] = 0
            que.append((y, x))

cnt = 0
while que:
    y, x = que.popleft()
    for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        ny = y + iy
        nx = x + ix
        if painted[ny][nx] == '.':
            painted[ny][nx] = painted[y][x] + 1
            que.append((ny, nx))

print(painted[y][x])


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    # 蛮兵
    painted = [['#'] * (w + 2)]
    painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
    painted.append(['#'] * (w + 2))
    que = []

    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if painted[y][x] == '#':
                painted[y][x] = 0
                que.append((y, x))
    while que:
        qq = []
        for y, x in que:
            if painted[y - 1][x] == '.':
                painted[y - 1][x] = painted[y][x] + 1
                qq.append((y - 1, x))
            if painted[y + 1][x] == '.':
                painted[y + 1][x] = painted[y][x] + 1
                qq.append((y + 1, x))
            if painted[y][x + 1] == '.':
                painted[y][x + 1] = painted[y][x] + 1
                qq.append((y, x + 1))
            if painted[y][x - 1] == '.':
                painted[y][x - 1] = painted[y][x] + 1
                qq.append((y, x - 1))
        que = qq

    print(painted[y][x])


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

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
com = 1
check_list = [1]
count = {i + 1:0 for i in range(n)}
while check_list:
    check = check_list.pop(0)
    next_check = graph[check]
    for i in range(len(next_check)):
        count[next_check[i]] += i
        check_list.append(next_check[i])
        graph[next_check[i]].remove(check)
    if check == 1:
        com *= k
    elif check in graph[1]:
        com *= k - 1 - count[check]
        com %= mod
    else:
        com *= k - 2 - count[check]
        com %= mod
print(com)

### FIXED CODE ###

import collections

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag[1] = True
queue = collections.deque([1])
ans = k
while queue:
    test = queue.popleft()
    temp = [flag[graph[test][i]] for i in range(len(graph[test]))].count(True)
    num = 0
    for i in range(len(graph[test])):
        if flag[graph[test][i]] == True:
            continue
        ans *= (k - temp - num - 1)
        ans %= mod
        num += 1
        queue.append(graph[test][i])
        flag[graph[test][i]] = True
print(ans)
### BUGGY CODE ###

# 最小公倍数(ユーグリッド互除法)
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd( b, a % b)


K = int(input()) +1
mydict = {}

# データパターンを求める式
ans = 0
for h in range(1, K):
  for i in range(1, K):
    for j in range(1, K):
      
      tmp = ''.join(map(str, sorted([h,i,j])))
      if tmp in mydict:
        ans += mydict[tmp]
      else:
        val = gcd(h,gcd(i,j))
        ans += val
        mydict[tmp] = val 

print(ans)


### FIXED CODE ###

# 最小公倍数(ユーグリッド互除法)
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd( b, a % b)

K = int(input()) + 1
mydict = {}

# データパターンを求める式
ans = 0
for h in range(1, K):
  ans += gcd(h,gcd(h,h))

  for i in range(h+1, K):
    ans += (gcd(h,gcd(h,i)) * 3)
    ans += (gcd(h,gcd(i,i)) * 3)

    for j in range(i+1, K):
      ans += (gcd(h,gcd(i,j)) * 6)

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

# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                adjmatrix[i][j] = 0
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                #adjmatrix[j][i] = adjmatrix[j][k] + adjmatrix[k][i]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)
       

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)
### BUGGY CODE ###

import itertools

T = input()
# T = 'PD?D??P'
# T = 'P?P?'

ans = []
h = T.count('?')
for v in itertools.combinations_with_replacement(['P', 'D'], h):
    # print(v)
    T2 = T
    i = 0
    while True:
        if '?' not in T2:
            break
        T2 = T2.replace('?', v[i], 1)
        i += 1
    d = T2.count('D')
    pd = T2.count('PD')
    ans.append([d+pd, T2])

# print(ans)
print(max(ans, key=lambda x: x[0])[1])


### FIXED CODE ###

T = input()
# T = 'PD?D??P'
# T = 'P?P?'

ans = ''
n = 0

T2 = T.replace('?', 'D')
d = T2.count('D')
pd = T2.count('PD')
if n < d+pd:
    n = d+pd
    ans = T2

T2 = T.replace('?D', 'PD')
T2 = T2.replace('?', 'D')
d = T2.count('D')
pd = T2.count('PD')
if n < d+pd:
    n = d+pd
    ans = T2

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

n = int(input())
a = [0] + list(map(int,input().split())) + [0]
sa = [abs(a[i]-a[i+1]) for i in range(n+1)]

for i in range(n):
    yen = sum(sa) + abs(a[i+2]-a[i]) - sa[i] - sa[i+1]
    print(yen)

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int,input().split())) + [0]
sa = [abs(a[i]-a[i+1]) for i in range(n+1)]
sum_sa = sum(sa)

for i in range(n):
    yen = sum_sa + abs(a[i+2]-a[i]) - sa[i] - sa[i+1]
    print(yen)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
m = [0] * MAX
for i in range(n):
  m[a[i]] += 1
#print(m[:30])
mx = max(a)
ans = 0
for i in range(2, mx + 1):
  if m[i] != 1:
    continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

sieve = [True] * MAX
counts = [0] * MAX
a.sort()
ans = 0
sieve[0] = False
sieve[1] = False
for i in range(n):
  counts[a[i]] += 1
  if not sieve[a[i]]:
    continue
  for j in range(a[i]*2, MAX, a[i]):
    sieve[j] = False
  if counts[a[i]] == 1:
    ans += 1
  elif counts[a[i]] == 2:
    ans -= 1
    
print(ans)