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

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
prev = [0]
for i, a in enumerate(A):
    temp = []
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = 1 << j
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1])

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N+1)]
for s in range(1 << N):
    temp = 0
    for n in range(N):
        if s & (1 << n): temp += 1
    cands[temp].append(s)
for i, a in enumerate(A):
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in cands[i]:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += (first * x // A[i]) % MOD

print(answer%MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

print(answer%MOD)
### BUGGY CODE ###


for i in range(10**11):
    pass



### FIXED CODE ###

S = input()
if S[2]==S[3] and S[4]==S[5]:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    while money>=ls[i]:
      money-=ls[i]
      stock+=1
  elif ls[i]>ls[i+1]:
    money+=ls[i]*stock
    stock=0
money+=ls[N-1]*stock

print(money)

### FIXED CODE ###

N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    s=money//ls[i]
    money-=s*ls[i]
    stock+=s
  elif ls[i]>ls[i+1]:
    money+=ls[i]*stock
    stock=0
money+=ls[N-1]*stock

print(money)
### BUGGY CODE ###

from itertools import chain
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
t=[]
for i in range(min(n,m)):
    t.append([bc[i][1]]*bc[i][0])
t=list(chain.from_iterable(t))

ans=sum(a)
j=0
while j<len(t) and j<n and t[j]>a[j]:
    ans+=t[j]-a[j]
    j+=1

print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
t=[]

for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n,a,b=map(int,input().split())
x=n//(a+b)
x*=a
if a!=0:
    for i in range(n%(a+b)):
        x+=1
        a-=1
        if a==0:
            break
print(x)    

### FIXED CODE ###

n,a,b=map(int,input().split())
x=n//(a+b)
x*=a
if a!=0:
    if n%(a+b)<a:
        x=x+(n%(a+b))
    else:
        x+=a
print(x)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
A = [list(map(int,input().split())) for _ in range(Q)]
AC_list = []
for i in range(N-1):
    if S[i:i+2] == 'AC':
        AC_list.append(1)
    else:
        AC_list.append(0)
for a in A:
    check = AC_list[a[0]-1:a[1]-1]
    print(sum(check))


### FIXED CODE ###

import numpy as np
N,Q = map(int,input().split())
S = np.array(list('_' + input()), dtype='U2')
A = (S == 'A')
C = (S == 'C')
AC = (A[:-1] & C[1:])
AC_cum = AC.cumsum()

for _ in range(Q):
    L,R = map(int,input().split())
    print(AC_cum[R-1] - AC_cum[L-1])
### BUGGY CODE ###

N, = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
def g(x):
    mx, mn = N, -1
    idx = mx//2
    while mx-mn>1:
        if Q[idx] >= x:
            mx, idx = idx, (idx+mn)//2
            continue
        mn, idx = idx, (idx+mx)//2
    return idx+1
    
def f(x):
    # q < x の数を探す
    c = 0
    for i, q in enumerate(Q):
        if q < x:
            c+=1
    return c
mxk = 29
msk = (1<<mxk) - 1
msk2 = (1<<(mxk-1))
r = 0
for i in range(mxk):
    # 下からiビット目をみる
    for j in range(N):
        Q[j] = Q[j] & msk
        P[j] = P[j] & msk
    msk >>= 1
    Q.sort()
#    print(mxk-1-i, P)
#    print(Q)
    b = 0
    for p in P:
        if p & msk2:
            # i bit が1になる
            # q < msk2 - p&msk
            # msk2 <= q < 2*msk2 - p
            # 0
            # msk2-p&msk <= q < msk2 
            # 2*msk2 - p <= q
            x = g(2*msk2 - (p&msk))
            z = g(msk2 - (p&msk))
#            print(x, y, z, msk2)
            b += z+N-x
#            print(p, z+N-x, msk2)
        else:
            x = g(2*msk2 - (p&msk))
            z = g(msk2 - (p&msk))
#            print(p, x, y, z)
#            print(2*msk2 - p&msk, msk2, msk2 - p&msk)
            b += x-z
#            print(p, x-z)
#    print(b)
    if b%2:
        r += 1<<(mxk-1-i)
    msk2 >>= 1
print(r)


### FIXED CODE ###

N, = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
mxk = 29
msk = (1<<mxk) - 1
msk2 = (1<<(mxk-1))
r = 0
for i in range(mxk):
    # 下からiビット目をみる
    for j in range(N):
        Q[j] = Q[j] & msk
        P[j] = P[j] & msk
    msk >>= 1
    P.sort()
    Q.sort()
    j1 = N-1
    j2 = N-1
    b = 0
    ss = N
#    print(P, Q)
    for l in range(N):
        if P[l] & msk2:
            ss = l
            break
        k1 = msk2 - (P[l]&msk)
        k2 = k1 + msk2
        while j1 >= 0:
            if Q[j1] < k1:
                break
            j1 -= 1
        while j2 >= 0:
            if Q[j2] < k2:
                break
            j2 -= 1
        b += j2 - j1
#        print("a",j2-j1,k1,k2,j1,j2)

    j1 = N-1
    j2 = N-1
#    print(ss)
    for l in range(ss, N):
        k1 = msk2 - (P[l]&msk)
        k2 = k1 + msk2
        while j1 >= 0:
            if Q[j1] < k1:
                break
            j1 -= 1
        while j2 >= 0:
            if Q[j2] < k2:
                break
            j2 -= 1
#        print("b",j1 - j2 + N)
        b += j1 + N - j2

#    b = 0
#    for p in P:
#        if p & msk2:
#            x = g(2*msk2 - (p&msk))
#            z = g(msk2 - (p&msk))
#            b += z+N-x
#        else:
#            x = g(2*msk2 - (p&msk))
#            z = g(msk2 - (p&msk))
#            b += x-z
#    print(b, r, i)
    if b%2:
        r += 1<<(mxk-1-i)
    msk2 >>= 1
print(r)
### BUGGY CODE ###

s = int(input())
length = len(str(s))

ans = []
for i in range(length):
    for j in range(i, length):
        n = int(str(s)[i:j+1])
        if n % 2019 == 0:
            ans.append(n)

print(len(ans))

### FIXED CODE ###

S = input()

mod = 2019
cnt = [0] * 2019
cur = 0  # 現在検討中の部分文字列
cnt[cur] = 1
d = 1   # 桁

for s in S[::-1]:
    cur += int(s) * d
    cur %= mod
    cnt[cur] += 1
    d *= 10
    d %= mod

ans = 0
for c in cnt:
    ans += c * (c-1) // 2

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

import itertools
n = int(input())


def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return r


p = prime_factorize(n)
ans = 10**13
pr0 = 1

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+n//pr-2)

print(ans)

### FIXED CODE ###

n = int(input())

ans = 10**13
for i in range(1, int(n**0.5//1)+1):
    if n%i == 0:
        ans = min(ans, i+n//i-2)
print(ans)
### BUGGY CODE ###

e=enumerate
n,a=open(0)
d=[0]+[-1e18]*2001
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*abs(~i-j+k+int(n)),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

### FIXED CODE ###

e=enumerate
n,*a=map(int,open(0).read().split())
dp=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):dp=[dp[0]+a*abs(n-j-i-1)]+[max(dp[k]+a*abs(n-j+k-i-1),dp[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[dp[j]+a*abs(i-j)]
print(max(dp))
### BUGGY CODE ###

import math
n = int(input())
for i in range(int(math.sqrt(n)),n+1,1):
    if n%i==0:
        break
print(len(str(i)))


### FIXED CODE ###

import math
n = int(input())
for i in range(int(math.sqrt(n)),0,-1):
    if n%i==0:
        a=n//i
#        print(i)
        print(max(len(str(i)),len(str(a))))
        break
### BUGGY CODE ###

(n,m) = map(int,input().split())
a,A,b,me,d,w,s = [0]*m,[0]*m,[-1]*n,[1]*n,[0]*n,[0]*m,(n*(n-1))//2
for i in range(m):
    (a[i], A[i]) = map(int,input().split())
    a[i] -= 1
    A[i] -= 1
w[m-1] = s
 
def se(i, b):
     m = 0
     while b[i] >= 0:
          i = b[i]
          m += 1
     return i,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = a[i],A[i]
     p1,m1 = se(i1, b)
     p2,m2 = se(i2, b)
     if p1 != p2:
          if d[m1] < d[m2]:
               (p1,p2) = (p2,p1)
          b[p2] = p1
          s -= me[p1]*me[p2]
          me[p1] += me[p2]
          me[p2] = 0
          d[p1] = max(d[p1],d[p2]+1)
     w[i-1] = s
         
for i in range(m):
     print(w[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
for b, c in BC:
    i = bisect.bisect_left(A, c)
    if i == 0:
        break
    else:
        start = min(i, b)
        conect = [c for j in range(start)]
        A.extend(conect)
        A = A[start:]
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
D = []
for b, c in BC:
    D.extend([c for i in range(b)])
    if len(D) >= n:
        D = D[:n]
        break
for x in range(len(D)):
    if A[x] > D[x]:
        break
else:
    x += 1
print(sum(A[x:]) + sum(D[:x]))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

# dp[i] = 足場iに移動するのに必要な最小コスト
dp = [0 for _ in range(N)]


def get_costs(i):
    """足場iに1回で辿り着くためのコストをイテレータで返す"""
    # 足場iへ1回で行く方法は1～KのK通り
    for k in range(K):
        k = k + 1
        # 出発点がマイナスになるようなルートはスキップ
        if i - k < 0:
            continue
        # print(f"i:{i} k:{k} cost:{dp[i - k] + abs(h[i] - h[i - k])}")
        # K歩進んだときのコストを返す
        yield dp[i - k] + abs(h[i] - h[i - k])


# DP配列更新
for i in range(1, N):
    # 最小コストで更新する
    # リストの中身がない場合は0とする
    dp[i] = min(list(get_costs(i)))

print(dp[-1])


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np

N, K = map(int, input().split())
h = list(map(int, input().split()))
# 高速化のためにnumpy使う
h = np.array(h)

# dp[i] = 足場iに移動するのに必要な最小コスト
dp = [0 for _ in range(N)]
# 高速化のためにnumpy使う
dp = np.array(dp)

# DP配列更新
"""
TLEだったやつ
for i in range(1, N):
    # 最小コストで更新する
    max_k = min([i, K]) + 1
    dp[i] = min([dp[i - k] + abs(h[i] - h[i - k]) for k in range(1, max_k)])
"""
for i in range(1, N):
    # 最小コストで更新する
    # K個まとめて移動コストを計算することで高速化
    # ただしマイナスからスタートするような値はスキップする
    s = max(0, i - K)
    dp[i] = np.min(dp[s:i] + np.abs(h[s:i] - h[i]))

print(dp[-1])
### BUGGY CODE ###

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

N,M = map(int,input().split())
#V=[[] for _ in range(N)]
row=[]
col=[]
data=[1]*(M)
for _ in range(M):
    a,b = map(int, input().split())
    row.append(a-1)
    col.append(b-1)

s=0
graph=coo_matrix((data, (row, col)), shape=(N,N))
dist_matrix,predecessors = dijkstra(csgraph=graph, directed=False, indices = s, unweighted=True, return_predecessors=True)
#print(dist_matrix)
#print(predecessor)
ans = [0]*(N-1)
for i,e in enumerate(predecessors[1:]):
    if e == -9999:
        print('No')
        exit()
    ans[i] = e+1
print('Yes')
print(*ans,sep='\n')

### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())
V=[[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
state=[0]*N
q=deque()
ans=[0]*(N)

state[0]=1
q.append(0)
while len(q) > 0:
    v=q.popleft()
    for u in V[v]:
        if state[u]==0:
            state[u]=1
            ans[u]=v+1
            q.append(u)
print('Yes')
print(*ans[1:],sep='\n')
### BUGGY CODE ###

import itertools

def main():
    N = int(input())
    S = input()
    d = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    #answer = set()
    cnt = 0
    for xx, yy, zz in itertools.permutations(('R', 'G', 'B'), 3):
        x, y, z = d[xx], d[yy], d[zz]
        for i in x:
            for j in y:
                if (j < i):
                    continue
                for k in z:
                    if k < j:
                        continue
                    elif k-j == j-i:
                        continue
                    #assert k > j > i
                    #answer.add((i+1, j+1, k+1))
                    cnt += 1
    print(cnt)
    #assert len(answer) == cnt
    #print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools
import bisect

def main():
    N = int(input())
    S = input()
    d = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    #answer = set()
    cnt = 0
    for xx, yy, zz in itertools.permutations(('R', 'G', 'B'), 3):
        x, y, z = d[xx], d[yy], d[zz]
        for i in x:
            y_start = bisect.bisect_left(y, i)
            for jj in range(y_start, len(y)):
                j = y[jj]
                assert i < j
                z_start = bisect.bisect_left(z, j)
                z_point = bisect.bisect_left(z, 2*j-i)
                #print(z_point, z)
                if (len(z) <= z_point) or (z[z_point] - j != j - i):
                    cnt += len(z) - z_start
                else:
                    cnt += len(z) - z_start - 1
                # for kk in range(z_start, len(z)):
                #     k = z[kk]
                #     assert j < k
                #     if k-j > j-i:
                #         #超えたのでもうチェックしなくていい
                #         cnt += len(z) - kk
                #         break
                #     elif k-j == j-i:
                #         cnt += len(z) - kk - 1
                #         break
                #     else:
                #         #assert k > j > i
                #         #answer.add((i+1, j+1, k+1))
                #         cnt += 1
    print(cnt)
    #assert len(answer) == cnt
    #print(answer)

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

n, q = list(map(int, input().split()))
s = input()
for i in range(q):
    l, r = list(map(int, input().split()))
    print(len(s[l - 1:r].split("AC")) - 1)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = (1 if s[i:i + 2] == "AC" else 0) + t[i]
for i in range(q):
    l, r = list(map(int, input().split()))
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

import numpy as np
n = int(input())  #nは入力回数
num_list = [list(map(int, input().split())) for _ in range(n)]
dp_ini=0
dp=np.zeros((n+1,3))
for i in range(0,n):
  for j in range(3):
    for k in range(3):
      if(j==k):
        continue
      else:
        dp[i+1][k]=max(dp[i+1][k],dp[i][j]+num_list[i][k])
print(int(max(dp[n][0],dp[n][1],dp[n][2])))

### FIXED CODE ###

def main():
  n = int(input())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(n)]

  dp = [[0] * 3 for i in range(n+1)]
  for i in range(0,n):
    for j in range(3):
      for k in range(3):
        if(j==k):
          continue
        else:
          dp[i+1][k]=max(dp[i+1][k],dp[i][j]+num_list[i][k])
  print(int(max(dp[n][0],dp[n][1],dp[n][2])))

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

# D - Ki
import sys
sys.setrecursionlimit(10**6)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

seen = [False]*N
cnt = [0]*N
def dfs(v,point,seen):
    seen[v] = True# v を訪問済みにする
    cnt[v] += point
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        dfs(next_v,point,seen)

for p,x in lst:
    seenC = seen.copy()
    dfs(p,x,seenC)
print(*cnt)

### FIXED CODE ###

# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
    
lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)
### BUGGY CODE ###

N = int(input())
ans = 0
if N == 1:
    print(ans)
else:
    for i in range(N-1):
        ans += i+1
    print(ans)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()

print(n*(n-1)//2)
### BUGGY CODE ###

import re
from collections import Counter
n, q = map(int, input().split())
s = input()
word = re.findall('AC', s)
C1 = Counter(word)
for _ in range(q):
    l, r = map(int, input().split())
    C2 = Counter(re.findall('AC', s[:l]))
    C3 = Counter(re.findall('AC', s[r-1:]))
    print(C1['AC']-(C2['AC']+C3['AC']))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m+1)
    d[1] = 1
    for i in range(2, m+1):
        for j in range(i, m+1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 1
    for i in a:
        ps = set()
        while i != 1:
            p = d[i]
            ps.add(p)
            i = i // d[i]
        if f:
            if b & ps:
                f = 0
            b |= ps
        c &= ps

    if f:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m+1)
    d[1] = 1
    for i in range(2, m+1):
        for j in range(i, m+1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 1
    for i in a:
        ps = set()
        while i != 1:
            p = d[i]
            ps.add(p)
            i = i // d[i]
        if f:
            if b & ps:
                f = 0
            b |= ps
        c &= ps

    if f:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


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

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
lst = [A.count(a)%2 for a in set(A)]
print(sum(lst))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
As = sorted(A)
num = 0
i = 0
while i < N:
    count = 0
    j = As[i]
    while i < N and As[i] == j:
        count += 1
        i += 1
    if count % 2 == 1:
        num += 1
print(num)
### BUGGY CODE ###

import math
s=0
n, m=map(int, input().split())
mm = int(m)
t = {}

while s==0:
    for i in range(2,int(math.sqrt(mm))):
#         print(i)
        if m%i==0:
            m=m//i
            if m==1:
                s=1
            if i in t.keys():
                t[i]+=1
            else:
                t[i]=1
            break
out=1
def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) 

for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

### FIXED CODE ###

import math

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a)]
# line = [2] + list(range(3, m+2, 2))

for i in line:
# for i in range(2, m+2, 2):
#     print(i)
    cnt = 0
    while m%i==0:
        m=m//i
        cnt += 1

    if cnt>0:
        t[i]=cnt

    if m==1:
        break

if m!=1:
    t[m]=1

def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) 

out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
#     out = out%(1000000007)
print(out%(1000000007))
### BUGGY CODE ###

import collections

N = int(input())
A = [int(input()) for i in range(N)]

Adic = collections.Counter(A)

B = [n % 2 for n in Adic.values()]

while 0 in B:
    B.remove(0)

print(len(B))


### FIXED CODE ###

import collections

N = int(input())
A = [int(input()) for i in range(N)]

Adic = collections.Counter(A)

B = [n % 2 for n in Adic.values()]

print(B.count(1))