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

# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
AB = [[0] * 2 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    AB[i][0], AB[i][1] = a, b

K = 0
for i in range(N-1):
    K = max(len(graph[i]), K)

# BFSのためのデータ構造
que = deque()
dist = [False] * N

# 初期条件
que.append(0)
color_num = [[0] * N for _ in range(N)]
dist[0] = True
# BFS開始
while que:
    v = que[0]
    que.popleft()
    tmp = 0
    for new_v in graph[v]:
        if dist[new_v]:
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        # 色を塗る
        for k in range(tmp+1, K+1):
            if k in color_num[v]:
                continue
            else:
                color_num[v][new_v] = k
                color_num[new_v][v] = k
                tmp = k
                break

# 答えの出力
print(K)
for i in range(N-1):
    print(color_num[AB[i][0]][AB[i][1]])

### FIXED CODE ###

#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  if s[i] == 'G':
    g.append(i)
  if s[i] == 'B':
    b.append(i)
cnt = len(r)*len(g)*len(b)
for i in r:
  for j in g:
    a = abs(i-j)
    B = max(i,j)+a
    c = min(i,j)-a
    if (i+j)%2==0:
      d = (i+j)//2
    else:
      d=-1
    if B in b:
      cnt-=1
    if c in b:
      cnt-=1
    if d in b:
      cnt-=1
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()
r=S.count('R')
b=S.count('B')
g=S.count('G')
ans=r*b*g
for i in range(N):
    for s in range(N):
        j=i+s
        k=j+s
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

from collections import deque

n,m,k = map(int,input().split())

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    y.append(i)
    while len(y)>0:
        x = y.popleft()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            y.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')


### FIXED CODE ###

from collections import deque

n,m,k = map(int,input().split())

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    # if alre[i]==True:
    #     continue
    # gro[i]=set([i])
    y.append(i)
    leader = i
    cnt = 0 
    while len(y)>0:
        x = y.popleft()
        if parent[x]!=-1:
            continue
            # print(to)
        parent[x]=leader
        y.extend(cango[x])
        cnt +=1
    if cnt!=0:
        gro[leader]=cnt
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    # group = gro[parent[iam]]
    tmp_ans = gro[parent[iam]]
    tmp_ans -=1
    tmp_ans -= len(cango[iam])
    for block in cannotgo[iam]:
        if parent[block]==parent[iam] :
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')
### BUGGY CODE ###

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

is_possible = True
for i in range(n):
    if a[i] > 2**i - 1:
        is_possible = False
        break
if a[n] > 2**n:
    is_possible = False

s = 0
for i in range(n + 1):
    s += a[i] * (2**(n - i))
if s > 2**n:
    is_possible = False

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (a[i] + b[i]) * 2

c = [0] * (n + 1)
c[n] = a[n]
ans = a[n]
for i in reversed(range(n)):
    if (c[i + 1] + 1) // 2 + a[i] + b[i] > 2**i:
        is_possible = False
        break
    c[i] = min(c[i + 1], 2**i - a[i] - b[i]) + a[i]
    ans += c[i]

# print(a)
# print(b)
# print(c)

if is_possible:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

is_possible = True
for i in range(n):
    if a[i] > 2**i - 1:
        is_possible = False
        break
if a[n] > 2**n:
    is_possible = False

s = 0
for i in range(n + 1):
    s += a[i] * (2**(n - i))
if s > 2**n:
    is_possible = False

b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (a[i] + b[i]) * 2

c = [0] * (n + 1)
c[n] = a[n]
ans = a[n]
for i in reversed(range(n)):
    if (c[i + 1] + 1) // 2 + a[i] + b[i] > 2**i:
        is_possible = False
        break
    c[i] = min(c[i + 1], 2**i - a[i] - b[i]) + a[i]
    ans += c[i]

# print(a)
# print(b)
# print(c)

if is_possible:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

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


l_sum = []
r_sum = []
sum_list = []

l_c = 0
r_c = 0

for i in range(1,N):
	if S[i-1] == '#':
		l_c = l_c + 1
	l_sum.extend([l_c])
	if S[N-i] == '.':
		r_c = r_c + 1
	r_sum.insert(0,r_c)

l_sum.insert(0,0)
r_sum.extend([0])

sum_list = [x + y for (x,y) in zip(l_sum,r_sum)]
print(min(sum_list))


### FIXED CODE ###

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

c_b = 0
c_w = S.count('.')
sum = []

for i in S:
	if i == '.':
		c_w = c_w - 1
	sum.extend([c_b+c_w])
	if i == '#':
		c_b = c_b + 1

print(min(sum))
### BUGGY CODE ###

N = int(input())
s = input()
mod = 10 ** 9 + 7

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * 2) % mod
        if j-1 >= 0:
            dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % mod
        else:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod

pow2 = pow(2, len(s), mod)
inv_pow2 = pow(pow2, mod-2, mod)
print((dp[-1][len(s)] * inv_pow2) % mod)


### FIXED CODE ###

N = int(input())
s = input()
mod = 10 ** 9 + 7


def main():
    dp = [[0 for _ in range(N+1)] for _ in range(2)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(N):
            dp[(i+1)%2][j] = 0
        for j in range(N):
            dp[(i+1)%2][j+1] = (dp[(i+1)%2][j+1] + dp[i%2][j] * 2) % mod
            if j-1 >= 0:
                dp[(i+1)%2][j-1] = (dp[(i+1)%2][j-1] + dp[i%2][j]) % mod
            else:
                dp[(i+1)%2][j] = (dp[(i+1)%2][j] + dp[i%2][j]) % mod

    pow2 = pow(2, len(s), mod)
    inv_pow2 = pow(pow2, mod-2, mod)
    print((dp[N%2][len(s)] * inv_pow2) % mod)


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

n = int(input())

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

ans = 0
dx = 10 ** 9 + 7
alist = []
for i in range(n):
    for j in range(i+1, n):
        alist.append((a[i] * a[j]) % dx)

ans = sum(alist)
ans %= dx
print(ans)


### FIXED CODE ###

n = int(input())

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

S = sum(a)

S2 = sum(map(lambda x: x * x, a ))

ans = (S * S - S2) // 2 % 1000000007
print(ans)
### BUGGY CODE ###

import math

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

equal = 0
elements = set(A)
for e in elements:
    tmp = A.count(e)
    equal += tmp * (tmp - 1) // 2

for i in range(n):
    A_tmp = A[: i] + A[i + 1: ]
    equal_i = A_tmp.count(A[i])
    print(equal - equal_i)

### FIXED CODE ###

import math
import collections

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

equal = 0
elements = collections.Counter(A)
equal = sum([v * (v - 1) // 2 for v in elements.values()])

for i in range(n):
    equal_i = elements[A[i]] - 1
    print(equal - equal_i)
### BUGGY CODE ###

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

dp=[[0 for _ in range(N)] for _ in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ(i>j)

for i in range(N):
  if S[i]==S[N-1]:
    dp[i][N-1]=1
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in range(i):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if j+dp[i][j]-1>=i:
        dp[i][j]=i-j

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))

### FIXED CODE ###

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

dp=[[0 for _ in range(i)] for i in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ(i>j)

for i in range(N-1):
  if S[i]==S[N-1]:
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in range(i):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if j+dp[i][j]-1>=i:
        dp[i][j]=i-j

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))
### BUGGY CODE ###

a,b,n=map(int,input().split())
# s=n//b
nmax = (a*n)//b - a*(n//b)
# for i in range(1,s+1):
#     x = b*i-1
#     t = (a*x)//b - a*(x//b)
#     if t > nmax:
#         nmax = t
b_n = b
while b_n <= n:
    x = b_n -1
    t = (a*x)//b - a*(x//b)
    if t > nmax:
        nmax = t
    b_n += b
print(nmax)

### FIXED CODE ###

a,b,n=map(int,input().split())
s=n//b
nmax = (a*n)//b - a*(n//b)
# b_n = b
# b_nn = 0
# while b_n <= n:
#     x = b_n -1
#     t = (a*x)//b - a*b_nn
#     if t > nmax:
#         nmax = t
#     b_n += b
#     b_nn +=1
if s>0:
    x = b*s-1
    t = (a*x)//b - a*(s-1)
    if t > nmax:
        nmax = t
print(nmax)
### BUGGY CODE ###

x=int(input())
mx=1
for i in range(2,32):
  p=2
  while i**p<=x:
    if i**p > mx:
      mx = i**p
      p+=1
print(mx)

### FIXED CODE ###

x=int(input())
mx=1
for i in range(2,32):
  p=2
  while i**p<=x:
    if i**p > mx:
      mx = i**p
    p+=1
print(mx)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

anss = [0 for _ in range(n-1)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    for k in range(1, n): 
        cnt = 0 
        for i in range(n):
            if cnt > 3:
                break
            if dist[i]-dist[start] == k:
                anss[k-1] += 1
                cnt += 1
    
for i in range(n):
    bfs(i)
for i in range(n-1):
    print(anss[i]//2)


### FIXED CODE ###

#!/usr/bin/env python3
# TLE解
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

ans = [0 for _ in range(n)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    # for k in range(1, n):
    #     for i in range(n):
    #         if dist[i]-dist[start] == k:
    #             ans[k-1] += 1

    for i in range(n):
        ans[dist[i]] += 1
    
for i in range(n):
    bfs(i)
for i in range(1, n): 
    print(ans[i]//2)
### BUGGY CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]


NN = 10 ** 6 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
def prime_factrize(n):
    res = []
    while n != 1:
        prime = min_factor[n]
        exp = 0
        while min_factor[n] == prime:
            exp += 1
            n //= prime
        res.append([prime, exp])
    return res


n = INT()
a = LIST()
ll = []
for i in range(n):
    aa = prime_factrize(a[i])
    for j in range(len(aa)):
        try:
            idx = [ll[k][0] for k in range(len(ll))].index(aa[j][0])
            ll[idx][1] = max(ll[idx][1], aa[j][1])
        except:
            ll.append(aa[j])
l = 1
for i in range(len(ll)):
    l *= pow(ll[i][0], ll[i][1], mod)
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
keys = [0] * n
dic = {i: [] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        dic[a - 1].append(b -1)
        q.append(b - 1)
        keys[b - 1] = 1
    elif b == 1:
        dic[b - 1].append(a - 1)
        q.append(a - 1)
        keys[a - 1] = 1
    else:
        dic[a - 1].append(b - 1)
        dic[b - 1].append(a - 1)

while len(q) > 0:
    next = q.popleft()
    for i in dic[next]:
        if keys[i]:
            continue
        if i not in q:
            q.append(i)
            keys[i] = next + 1
print('Yes')
print(*keys[1:], sep='\n')

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
v[0] = 1
while q:
    next = q.popleft()
    for i in t[next]:
        if v[i - 1] == -1:
            q.append(i)
            v[i - 1] = next
print('Yes')
print(*v[1:], sep='\n')
### BUGGY CODE ###

import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import functools
@functools.lru_cache(maxsize=None)
def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod

def tami(n, r):
  if r == 0:
    res = kaizyou[n]
    return res %mod
  elif r == 1:
    res = kaizyou[n-1] * (n-1)
    return res %mod
  else:
    return (tami(n-1, r-1) + tami(n-1, r-2) )%mod

N,M = IL()

kaizyou = [0,1]
for i in range(2,N+1):
  kaizyou.append(kaizyou[-1]*i %mod)

ans = 0
for i in range(max(0, 2*N-M), N+1):
  ans += ((combi(N, i) * combi(M-N, N-i) ) %mod * tami(N, i)) %mod
print((((combi(M, N) * kaizyou[N]) %mod) * ans) %mod)

### FIXED CODE ###

import sys
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import functools
@functools.lru_cache(maxsize=None)
def factrial_memo(n):
  fact = [1, 1]
  for i in range(2, n + 1):
    fact.append((fact[-1] * i) % mod)
  return fact

def permutation(n,r): #nPr
  return fact[n]*pow(fact[n-r],mod-2,mod)%mod
  
def combination(n,r): #nCr
  return permutation(n,r)*pow(fact[r],mod-2,mod)%mod

def homogeneous(n,r): #nHr
  return combination(n+r-1,r)%mod

N,M = IL()

fact = factrial_memo(10**6)

s = 0
for k in range(1,N+1):
  s += combination(N, k) * permutation(M-k, N-k) * (-1)**(k-1)
ans = (permutation(M, N)**2 - s*permutation(M, N)) %mod
print(ans)
### BUGGY CODE ###


a,b,c,k = map(int,input().split())
ans = 0




for i in range(0,k):
    if not(a==0) :
        a = a-1
        ans +=1
        k=k-1
    elif not(b==0) :
        b=b-1
        k=k-1
    else:
        k -=1
        ans -=1
print(ans)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = 0

kk=k-a
for i in range(1):
    if kk<0:
        ans=k
        k=-1
        break
    else:
        ans = a
        k=k-a
    kk = k-b
    if kk<0:
        k=-1
        break
    else:
        k=k-b

    kk = k-c

    if kk<0:
        ans=ans-k
    elif kk>=0:
        ans=ans-c
print(ans)
### BUGGY CODE ###

# D - Not Divisible
import numpy as np
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
dbl = set([i[0] for i in c.items() if i[1] >= 2])

A.sort()
A = np.array(A)
ans = 0
for i in range(N):
    if A[i] == 0:
        continue
    elif A[i] not in dbl:
        ans += 1
    B = A % A[i]
    B = B.astype(np.bool)
    A = A * B

print(ans)

### FIXED CODE ###

# D - Not Divisible
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
ng = set([i[0] for i in c.items() if i[1] >= 2])
A.sort()

M = max(A)
primes = []
is_prime = [True] * (M+1)
for i, a in enumerate(A):
    if is_prime[a]:
        if a not in ng:
            primes.append(a)
        for j in range(a*2, M+1, a):
            is_prime[j] = False
print(len(primes))
### BUGGY CODE ###

N = int(input())

List=[''.join(sorted(input())) for i in range(N)]
List.sort()
List.extend("1")
cnt = 0

for i in range(N):
  a = List[i]
  b = List[i+1]
  if a != b:
    c = List.count(a)
    cnt = cnt + c * (c-1) / 2

print(int(cnt))

### FIXED CODE ###

N = int(input())

List=[''.join(sorted(input())) for i in range(N)]
List.sort()
List.extend("1")
cnt = 0
num = 0

for i in range(N):
  a = List[i]
  b = List[i+1]
  if a != b:   
    cnt = cnt + num * (num+1) / 2
    num = 0 
  else:
    num = num + 1

print(int(cnt))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))
### BUGGY CODE ###

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

mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for nn in range(2,n+1):
    if nn in a:
        dp[nn]=0
#    if nn-1 in a:
    else:
        dp[nn]=(dp[nn-1]+dp[nn-2])%mod

#print(dp)
print(dp[n])


### FIXED CODE ###

n,m=map(int,input().split())
a=set()
for i in range(m):
    ai=int(input())
    a.add(ai)


mod=10**9+7

t=[0]*(n+1)
t[0]=1

if 1 in a:
    t[1]=0
else:
    t[1]=1

for i in range(2,n+1):
    if i in a:
        t[i]=0
    else:
        t[i]=(t[i-1]+t[i-2])%mod

print(t[n])
### BUGGY CODE ###

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

dp = [float('inf') for _ in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    k = 0
    p = 1
    for x in c:
        k += 2 ** (x-1)
    for j in range(2 ** n):
        L = j | k
        dp[L] = min(dp[L], dp[j] + a)

#print(dp)

if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf') for _ in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    k = 0
    p = 1
    for x in c:
        k += 2 ** (x-1)
    for j in range(2 ** n):
        L = j | k
        dp[L] = min(dp[L], dp[j] + a)

#print(dp)

if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [None] * Q
for _ in range(Q):
    lr[_] = list(map(int, input().split()))
for _ in range(Q):
    ans = S[lr[_][0] - 1:lr[_][1]].count("AC")
    print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = len(S)
ACnum = [0] * L
for i in range(1, L):
    ACnum[i] += ACnum[i - 1]
    if S[i - 1] == "A" and S[i] == "C":
        ACnum[i] += 1

lr = [None] * Q
for _ in range(Q):
    lr[_] = list(map(int, input().split()))

for i in range(Q):
    ans = ACnum[lr[i][1] - 1] - ACnum[lr[i][0] - 1]
    print(ans)