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

A,B = map(int,input().split())

while B:
    A,B = B, A%B
g = A
g_ = g

count = 0
l = []
i = 2
while i <= g_:
    while g%i == 0:
        g = g/i
        l.append(i)
    l = list(set(l))
    i = i+1

print(1+len(l))

### FIXED CODE ###

A,B = map(int,input().split())

def gcd(x,y):
    while y:
        x,y = y, x%y
    return x

g = gcd(A,B)

count = 0
l = []

while g%2 == 0:
    l.append(2)
    g //= 2
i = 3
while i**2 <= g:
    if g%i == 0:
        l.append(i)
        g //= i
    else:
        i += 2
if g != 1:
    l.append(g)

print(len(set(l))+1)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  # row = list(input())
  row = readline().rstrip()
  blocks += row.count("#")
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  # visited.append((r,c))
  # visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc]: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )


### FIXED CODE ###

import sys
readline = sys.stdin.readline
from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  # row = list(input())
  row = readline().rstrip()
  blocks += row.count("#")
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  # visited.append((r,c))
  # visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc] or (nr,nc,step+1) in q: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )
### BUGGY CODE ###

#coding:utf-8

def main():
    n, q = map(int, input().split())
    s = input()
    slist = list(s)
    point = []
    for i in range(q):
        c = 0
        l, r = map(int, input().split())
        for j in range(l-1,r-1):
            if slist[j] == 'A' and slist[j+1] == 'C':
                c += 1
            else:
                pass
        point.append(c)

    for k in range(len(point)):
        print(point[k])


if __name__ == "__main__":
    main()

### FIXED CODE ###

#coding-utf:8

def main():
    n, q = map(int, input().split())
    s = input()
    t = [0] * (n+1)
    for i in range(n):
        if s[i : i+2] == 'AC':
            x = 1
        else:
            x = 0
        t[i+1] = t[i] + x
        x = 0

    for j in range(q):
        l, r = map(int, input().split())
        print(t[r-1] - t[l-1])

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

n = int(input())
ans = 1
for i in range(1, n + 1):
    ans *= i
ans %= 10 ** 9 + 7
print(ans)

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(n):
    ans *= i + 1
    ans %= 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

def solve():
    s = input()
    n = len(s)
    mod = 2019

    reminder = [0]*mod
    pre_rem = 0

    for i in range(n):
        pre_rem = (int(s[-i-1])*pow(10, i) + pre_rem) % mod
        reminder[pre_rem] += 1

    ans = reminder[0]  # そのまま割り切れる奴ら
    for rem_num in reminder[1:]:  # _nC_2をしてる
        ans += (rem_num * (rem_num -1))//2
    print(ans)
    
solve()

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

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

passwords = []
for i in range(len(S) - 2):
    for j in range(i + 1, len(S) - 1):
        # for k in range(j + 1, len(S)):
        for char in list(set(S[j + 1:])):
            password = S[i] + S[j] + char
            passwords.append(password)


# print(len(passwords))
# print(passwords)
# print(set(passwords))
print(len(list(set(passwords))))


### FIXED CODE ###

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

passwords = []
for i in range(0, 10):
    for j in range(0, 10):
        for k in range(0, 10):
            password = str(i) + str(j) + str(k)
            passwords.append(password)

char_hash = {}
for i, char in enumerate(S):
    if char in char_hash.keys():
        char_hash[char].append(i)
    else:
        char_hash[char] = [i]

# print(char_hash

count = 0
for password in passwords:
    exist_keys = char_hash.keys()
    # print(password[0] in char_hash.keys())
    if not(password[0] in exist_keys):
        continue
    if not(password[1] in exist_keys):
        continue
    if not(password[2] in exist_keys):
        continue
    first_index = min(char_hash[password[0]])
    second_indexes = char_hash[password[1]]
    second_index = -1
    for index in second_indexes:
        if index <= first_index:
            continue
        else:
            second_index = index
            break
    third_indexes = char_hash[password[2]]
    third_index = -1
    for index in third_indexes:
        if index <= second_index:
            continue
        else:
            third_index = index
            break
    # print(first_index, second_index, third_index)
    if first_index < second_index and second_index < third_index:
        count += 1

print(count)
# print(len(passwords))
# print(passwords)
# print(set(passwords))
# print(len(list(set(passwords))))
### BUGGY CODE ###

n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = []
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = dv.copy()
        dv_[i] = 1
        ret.append(dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return min(ret)
print(dfs([0]*len(r),0,0))

### FIXED CODE ###

n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
for x,y,z in node:
    dp[x][y] = z
    dp[y][x] = z
for i in range(n+1):
    dp[i][i] = 0
def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    return d
dp = wf(dp,n+1)
import copy
import sys
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = sys.maxsize
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))
### BUGGY CODE ###

import itertools
N = int(input())
L = sorted(list(map(int, input().split())))
D = list(itertools.combinations(L,3))
M = [1 for a,b,c in D if a + b > c ]
print (sum(M))

### FIXED CODE ###

import bisect
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N-1,1,-1):
  for j in range(i-1,0,-1):
    t = bisect.bisect(L, L[i]-L[j])
    if j-t>0: ans+=j-t
print (ans)
### BUGGY CODE ###

from itertools import permutations
from collections import defaultdict
from heapq import heappush, heappop


def solve(n, m, r):
    ans = 10**18
    g = defaultdict(list)
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        g[s-1].append((length, t-1))
        g[t-1].append((length, s-1))

    d = []
    for k in range(n):
        d.append(dijkstra(n, g, k))

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


def dijkstra(vertex, g, sp):
    d = [float('inf')] * vertex
    d[sp] = 0
    heap = [(d[sp], sp)]

    while heap:
        du, u = heappop(heap)
        for length, v in g[u]:

            if d[v] > du + length:
                d[v] = du + length
                heappush(heap, (d[v], v))
    return d


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))


### FIXED CODE ###

from itertools import permutations


def solve(n, m, r):
    ans = 10**18
    d = [[10**18]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

    for i in range(n):
        d[i][i] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dt = d[i][k] + d[k][j]
                if dt < d[i][j]:
                    d[i][j] = dt

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))
### BUGGY CODE ###

import numpy as np
N = int(input())
P = np.array(list(map(int, input().split())))

def get_the_i(P, n):
    return np.argmin(P[:n])

i = np.argmin(P)
count = 1
while(i > 0):
    i = get_the_i(P, i)
    count += 1
    
print(count)
    

### FIXED CODE ###


import numpy as np
N = int(input())
P = np.array(list(map(int, input().split())))

MIN = P[0]
count = 1
for p in P[1:]:
    if p < MIN:
        count += 1
        MIN = p

print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
ans = sum(a_list)
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list += [c]*b
a_list.sort()
m_list.sort(reverse=True)
for a, m in zip(a_list, m_list):
    if a < m:
        ans += (m-a)
    else:
        break
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list.append([c, b])
m_list.sort(reverse=True)
cnt = 0
tmp_list = []
for c, b in m_list:
    if cnt < n:
        tmp_list += [c]*b
    else:
        break
    cnt += b
a_list.extend(tmp_list)
a_list.sort(reverse=True)
print(sum(a_list[:n]))
### BUGGY CODE ###

"""
References
----------
[1]. kmjp. AtCoder ABC #144 : F - Fork in the Road, <http://kmjp.hatenablog.jp/entry/2019/10/28/0930>, kmjp's blog
[2]. parsely. https://atcoder.jp/contests/abc144/submissions/8200791, AtCoder.
[3]. physics0523. Fork in the Road(ABC144-F), <https://physics0523.hatenablog.com/entry/2019/10/27/235334>, physics0523's 精進ログ
"""
from copy import copy
INF = 10**9
def solve(n, m, s, t):
    E = [[] for i in range(n+1)]
    for i in range(m):
        u, v = s[i], t[i]
        E[u].append(v)
    dp = [INF] * (n+1)
    dp[n] = 0
    for i in range(n-1, 0, -1):
        v = [dp[j] for j in E[i]]
        dp[i] = 1 + sum(v) / len(v)
    dp2 = copy(dp)
    res = dp[1]
    for i in range(n-1, 0, -1):
        if len(E[i]) == 1:
            continue
        v = [dp[e] for e in E[i]]
        dp2[i] = 1 + (sum(v) - max(v)) / (len(v) - 1)
        for j in range(i-1, 0, -1):
            v = [dp2[k] for k in E[j]]
            dp2[j] = 1 + sum(v) / len(v)
        res = min(res, dp2[1])
        dp2[:i+1] = copy(dp[:i+1])
    return res

n, m = map(int, input().split())
s = [0] * m
t = [0] * m
for i in range(m):
    s[i], t[i] = map(int, input().split())
print(solve(n, m, s, t))

### FIXED CODE ###

"""
References
----------
[0]. 解説(公式), https://img.atcoder.jp/abc144/editorial.pdf, AtCoder
    - O(NM)
[1]. kmjp. AtCoder ABC #144 : F - Fork in the Road, <http://kmjp.hatenablog.jp/entry/2019/10/28/0930>, kmjp's blog
    - O(NM)
[2]. physics0523. Fork in the Road(ABC144-F), <https://physics0523.hatenablog.com/entry/2019/10/27/235334>, physics0523's 精進ログ
    - O(M)
[3]. Genki Ogaki. BC144 F - Fork in the Road考察＋参戦記, <https://www.onakasuitacity.com/abc144-f>, おじさん、今日プロ始
めるってよ
    - O(M)
"""
def solve(n, m, s, t):
    edges = [[] for i in range(n)]
    for i in range(m):
        u, v = s[i], t[i]
        edges[u-1].append(v-1)
    p = [0] * n
    p[0] = 1
    for i in range(n):
        for j in edges[i]:
            p[j] += p[i] / len(edges[i])
    E = [0] * n
    for i in range(n-2, -1, -1):
        v = [E[j] for j in edges[i]]
        E[i] = 1 + sum(v) / len(v)
    res = E[0]
    for i in range(n):
        deg = len(edges[i])
        if deg <= 1:
            continue
        k = max((E[j], j) for j in edges[i])[1]
        v = [E[j] for j in edges[i] if j != k]
        res = min(res, E[0] + p[i] * (sum(v) / (deg-1) - E[k]) / deg)
    return res

n, m = map(int, input().split())
s = [0] * m
t = [0] * m
for i in range(m):
    s[i], t[i] = map(int, input().split())
print(solve(n, m, s, t))
### BUGGY CODE ###

N=int(input())
S=str(input())
result = N
for i in range(N):
  S_1=S[:i]
  S_2=S[i+1:]
  result = min(result,S_1.count('W')+S_2.count('E'))
print(result)

### FIXED CODE ###

N=int(input())
S=str(input())

E=[0]*N
W=[0]*N
c=0
for i in range(N):
  W[i] =c
  if S[i]=='W':
    c +=1
c=0
for j in range(N):
  E[-1-j]=c
  if S[-1-j]=='E':
    c +=1
E=[E[0]]+E+[0]
W=[0]+W+[W[-1]]
answer=float('inf')
for i in range(N+2):
  answer=min(answer,E[i]+W[i])
print(answer)
### BUGGY CODE ###

n=int(input())
s=input()
R=[0]
G=[0]
B=[0]
for i in s:
  R.append(R[-1])
  G.append(G[-1])
  B.append(B[-1])
  if i=="R":R[-1]+=1
  elif i=="G":G[-1]+=1
  else:B[-1]+=1
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    if s[i]==s[j]:continue
    if "R" not in [s[i],s[j]]:
      ans+=R[-1]-R[j]
      if j+(j-i)<n:
        if s[j+(j-i)]=="R":ans-=1
    if "G" not in [s[i],s[j]]:
      ans+=G[-1]-G[j]
      if j+(j-i)<n:
        if s[j+(j-i)]=="G":ans-=1
    if "B" not in [s[i],s[j]]:
      ans+=B[-1]-B[j]
      if j+(j-i)<n:
        if s[j+(j-i)]=="B":ans-=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
R=[0]
G=[0]
B=[0]
for i in s:
  R.append(R[-1])
  G.append(G[-1])
  B.append(B[-1])
  if i=="R":R[-1]+=1
  elif i=="G":G[-1]+=1
  else:B[-1]+=1
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    if s[i]==s[j]:continue
    if "R" not in [s[i],s[j]]:
      ans+=R[-1]-R[j]
      if j+(j-i)<n:
        if s[j+(j-i)]=="R":ans-=1
    if "G" not in [s[i],s[j]]:
      ans+=G[-1]-G[j]
      if j+(j-i)<n:
        if s[j+(j-i)]=="G":ans-=1
    if "B" not in [s[i],s[j]]:
      ans+=B[-1]-B[j]
      if j+(j-i)<n:
        if s[j+(j-i)]=="B":ans-=1
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())

listLR = [a for a in range(L, R+1)]

flg = 0
for i in range(len(listLR)):
    if listLR[i] % 2019 == 0:
        flg = 1
        break

ans = 0
modL = L % 2019
modR = R % 2019
min2019 = 2019

if flg == 1:
    print(0)
elif modL <=3 and modR >=673:
    print(0)
else:
    for j in range(modL, modR+1):
        for k in range(j+1, modR+1):
            if j * k % 2019 < min2019:
                min2019 = j * k % 2019
    print(min2019)

### FIXED CODE ###

L, R = map(int, input().split())
modL = L % 2019
modR = R % 2019
min2019 = 2019

if R - L >= 2018:
    print(0)
else:
    for j in range(modL, modR+1):
        for k in range(j+1 , modR+1):
            min2019 = min(min2019, j * k % 2019)
    print(min2019)
### BUGGY CODE ###

import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[-1,0]
while count!=n*(n-1)//2:
  if check[len(check)-2]==check[len(check)-1]:
    print(-1)
    sys.exit()
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check.append(count)
print(day)

### FIXED CODE ###

import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[0,0]
while count!=n*(n-1)//2 and day<=10**4:
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check[0]=check[1]
  check[1]=count
  if check[0]==check[1]:
    print(-1)
    sys.exit()
if day>10**4:
  print(n*(n-1)//2)
  sys.exit()
print(day)
### BUGGY CODE ###

#!python3

# input
s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[(0, "")] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                a, b = dp[i - 1][j - 1]
                dp[i][j] = (a + 1, b + s[i - 1])
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = dp[-1][-1][1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

# input
s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[0] * (tn + 1) for _ in range(sn + 1)]
    w = [[None] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                w[i][j] = s[i - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    i, j = sn, tn
    while i != 0 and j != 0:
        if s[i - 1] == t[j - 1]:
            ans.append(w[i][j])
            i, j = i - 1, j - 1
        else:
            if dp[i][j - 1] < dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print("".join(ans[::-1]))


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

import sys
readline = sys.stdin.readline
from collections import Counter

def main():
    N, A = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    X = [x-A for x in X]
    ans = 0
    X1 = X[:N//2]
    X2 = X[N//2:]
    X1_sum = [0]
    for i in range(1, 2**len(X1)):
        b = bin(i)[2:].zfill(len(X1))
        su = sum([X1[i] for i, e in enumerate(b) if e == '1'])
        X1_sum.append(su)
    X2_sum = [0]
    for i in range(1, 2**len(X2)):
        b = bin(i)[2:].zfill(len(X2))
        su = sum([X2[i] for i, e in enumerate(b) if e == '1'])
        X2_sum.append(su)
    c = Counter(X2_sum)
    c_keys = c.keys()
    for x1 in X1_sum:
        if -x1 in c_keys:
            ans += c[-x1]

    print(ans - 1)

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, A = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    lim = max(X) * N
    X = [x-A for x in X]
    dp = [[0]*(2*lim) for _ in range(N+1)]
    dp[0][lim] = 1
    for i in range(1, N+1):
        x = X[i-1]
        for j in range(2*lim):
            if 0 <= j - x < 2 * lim:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-x]
            else:
                dp[i][j] = dp[i-1][j]
    
    print(dp[N][lim] - 1)


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

n = int(input())
a = list(map(int, input().split()))
dct = {}
for i in range(n):
    if a[i] in dct:
        dct[a[i]] += 1
    else:
        dct[a[i]] = 1
tmp_dct = {}
tmp2_dct = {}
for key, value in dct.items():
    tmp_dct[key] = value * (value - 1) // 2
    tmp2_dct[key] = (value - 1) * (value - 2) // 2
# print(tmp_dct, tmp2_dct)
ans_dct = {}
for key, value in dct.items():
    cnt = 0
    for key2, value2 in dct.items():
        if key == key2:
            cnt += tmp2_dct[key2]
        else:
            cnt += tmp_dct[key2]
        # print(key, key2, cnt)
    ans_dct[key] = cnt
# print(ans_dct)
for i in range(n):
    print(ans_dct[a[i]])

### FIXED CODE ###


def choose2(n):
    return n * (n-1) // 2

n = int(input())
a = list(map(int, input().split()))
dct = {}
for i in range(n):
    if a[i] in dct:
        dct[a[i]] += 1
    else:
        dct[a[i]] = 1
tot = 0
for key, value in dct.items():
    tot += choose2(value)
# print(tot)
for i in range(n):
    ans = tot
    ans -= choose2(dct[a[i]])
    ans += choose2(dct[a[i]]-1)
    print(ans)
### BUGGY CODE ###

n=input()
s=input()
n=int(n)
ans=0
com=[0 for _ in range(n*(n-1)*(n-2)//6)]
m=0
for i in range(n-2):
  x=int(s[i])
  for j in range(i+1,n-1):
    y=int(s[j])
    for k in range(j+1,n):
      z=int(s[k])
      com[m]=x*100+y*10+z
      m+=1
com=list(set(com))      
ans=len(com)
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
list=["" for _ in range(1000)]
ans=0
for i in range(1000):
  t=str(i)
  u="0"*(3-len(t))+t
  j=0
  exi=0
  p=u[0]
  for x in s:
    if x==p:
      j+=1
      if j==3:
        ans+=1
        break
      p=u[j]
    

  









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

from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

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

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = map(int, input().split())
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = map(int, input().split())
    add[p] += x


def dfs(now, fa):
    add[now] += add[fa]
    for i in v[now]:
        if i == fa:
            continue
        dfs(i, now)


dfs(1, 0)

for i in range(1, n + 1):
    print(add[i], end=' ')


### FIXED CODE ###

from sys import setrecursionlimit as SRL, stdin, stdout

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, q = rrd()

v = [[] for _i in range(n + 10)]

for i in range(n - 1):
    x, y = rrd()
    v[x].append(y)
    v[y].append(x)

add = [0] * (n + 10)

for i in range(q):
    p, x = rrd()
    add[p] += x

p = [(1, 0)]
vis = [0] * (n + 2)
while len(p):
    now, fa = p.pop()
    add[now] += add[fa]
    vis[now] = 1
    for i in v[now]:
        if not vis[i]:
            p.append((i,now))

stdout.write(" ".join(map(str, add[1:n + 1])))
### BUGGY CODE ###

A, B, N = input().split()
max = 0
for i in range(int(N)+1):
    temp = int(int(A)*i/int(B)) - int(A)*int(i/int(B))
    if temp > max:
        max = temp

print(max)

### FIXED CODE ###

A, B, N = input().split()
f = 0
if int(N) >= int(B):
    f = (int(B) - 1) / int(B)
    f = f - int(f)
else:
    f = int(N) / int(B)
    f = f - int(f)

print(int(f*int(A)))
### BUGGY CODE ###


import math

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

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

for i in range(M):
    max_A = max(A)
    A[A.index(max_A)] = math.floor((max_A) / 2)

print(sum(A))


### FIXED CODE ###


#優先度付きキュー
#値の追加 O(log|Q|)
#値の削除 O(log|Q|)
#最大値の取得 O(1)
#pythonでは 最小値のみしか取得できないため事前に全要素に-1をかけておき最後のまた-1かける

import math
import heapq

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

#各要素を-1倍
A = list(map(int,input().split()))
A = list(map(lambda x: x*-1,A))
heapq.heapify(A)

for i in range(M):
    max_A = heapq.heappop(A)
    max_A = max_A * -1
    heapq.heappush(A,-1* (math.floor((max_A) / 2)) )

print(-1 * sum(A))