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

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

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    set_primes = set_primes | res

if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import sys
input = sys.stdin.readline

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    for x in res:
        set_primes.add(x)
        
if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

s = list(input())
q = int(input())

f = 1
tail1 = []
head1 = []
for _ in range(q):
    i = list(map(str, input().split()))
    if i[0] == "1":
        f *= -1
    else:
        j,x,s1 = i
        if x == "1":
            if f == 1:
                head1 = [s1] + head1
            else:
                tail1 = tail1 + [s1]
        else:
            if f == -1:
                head1 = [s1] + head1
            else:
                tail1 = tail1 + [s1]

s2 = (head1 + s + tail1)
if f == -1:
    s2.reverse()

print("".join(s2))

### FIXED CODE ###

from collections import deque
 
S = input()
L = deque([])
for c in S:
    L.append(c)
Q = int(input())
flag = 1
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        flag *= -1
    else:
        F = q[1]
        if F == "1":
            if flag == 1:
                L.appendleft(q[2])
            else:
                L.append(q[2])
        else:
            if flag == 1:
                L.append(q[2])
            else:
                L.appendleft(q[2])
if flag == 1:
    print("".join(map(str, L)))
else:
    L.reverse()
    print("".join(map(str, L)))
### BUGGY CODE ###

import numpy as np


def f(A):
    N = len(A)
    cnt = 0
    
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                cnt += (A[k] < A[i] + A[j])
    return cnt


N = int(input())
A = np.int32(input().split())
A.sort()
print(f(A))


### FIXED CODE ###

import numpy as np
from numba import njit
 
@njit
def f(A):
  N = len(A)
  cnt = 0
  for i in range(N):
    for j in range(i + 1, N):
      for k in range(j + 1, N):
        cnt += (A[k] < A[i] + A[j])
  return cnt
 
N = int(input())
A = np.int32(input().split())
A.sort()
print(f(A))
### BUGGY CODE ###

from collections import defaultdict
    
n, m = map(int, input().split())
mp = 0

adj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    
for i in range(1, 1+n):
    q = [[i, 0]]

    while q:
        e, l = q.pop()

        if len(adj[e]) == 0:
            mp = max(mp, l)
        else:
            for j in adj[e]:
                q.append([j, l+1])

print(mp)

### FIXED CODE ###

import sys
from collections import defaultdict
    
sys.setrecursionlimit(10**9)
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    
dp = [-1]*(n+1)

def dfs(e):
    if dp[e] != -1:
        return dp[e]
    
    temp = 0
    for i in adj[e]:
        temp = max(temp, 1+dfs(i))
        
    dp[e] = temp
    return temp
    
    
for i in range(1, n+1):
    dfs(i)
    
print(max(dp))
### BUGGY CODE ###

N,K = map(int, input().split())
S = []
for i in range(K):
    L,R = map(int, input().split())
    S += [ j for j in range(L,R+1)]
S = set(S)

step = [0]*(N+1)
step[1] = 1

for j in range(1,N):
    for s in S:
        if j + s > N or step[j] == 0:
            continue
        step[j+s] += (step[j]%998244353)
        step[j+s] %= 998244353
print(step[N])

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
for i in range(k):
    lr[i][1] += 1

dp = [0]*n
dp[0] = 1
for i in range(1,n):
    dp[i] = dp[i-1]
    if i == 1:
        dp[1] = 0
    for l,r in lr:
        if i - l >= 0:
            dp[i] += dp[i-l]
        if i - r >= 0:
            dp[i] -= dp[i-r]
        dp[i] %= mod
print(dp[n-1])
### BUGGY CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b / gcd(a, b)


MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

l = 1
for a in A:
    l = lcm(l, a)

B = [l // a for a in A]

print(int(sum(B)) % MOD)


### FIXED CODE ###

from fractions import gcd

mod = 10 ** 9 + 7

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

lcm = 1
for s in A:
    lcm = s * lcm // gcd(lcm, s)

ans = lcm * sum([pow(s, mod - 2, mod) for s in A]) % mod

print(int(ans % mod))
### BUGGY CODE ###

S = input()
count = 0
while True:
    flag = []
    for i in range(len(S)):
        if i == 0:
            pre_s = S[i]
            flag.append(0)
        else:
            if pre_s != S[i] and flag[i-1] == 0:
                flag.append(1)
                flag[i-1] = 1
                pre_s = S[i]
            else:
                flag.append(0)
                pre_s = S[i]
            
    if sum(flag) == 0:
        break
    else:
        count += sum(flag)

    S = list(S)
    for i in range(len(flag)):
        if flag[i]:
            S[i] = "a"
    S = "".join(S).replace("a", "")
            
print(count)

### FIXED CODE ###

S = input()
a = S.count("0")
b = S.count("1")
if a<b:
    print(a*2)
else:
    print(b*2)
### BUGGY CODE ###

import numpy as np
from numba import njit

@njit(cache=True)
def main(N, s, dpt):
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1

    result = 0
    for i in range(N + 1):
        result = max(result, max(dpt[i]))

    return result

if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()], dtype='int32')

    dpt = np.array([[0] * (N + 1) for i in range(N + 1)])

    print(main(N, s, dpt))


### FIXED CODE ###

import numpy as np
from numba import njit
 
@njit(cache=True)
def main(N, s):
    dpt = np.zeros((N+1, N+1), dtype=np.int16)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
 
    return np.amax(dpt)
 
if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()]) 
 
    print(main(N, s))
### BUGGY CODE ###

n = input()
a = list(map(int, input().split()))
b= []
for i in range(len(a)):
    b.append(a[i]%(10**9+7))
sum = 0

for i in range(len(b)):
    for j in range(i,len(b)):
        if i<j:
            sum += (b[i]) * (b[j])
    
print(sum % (10**9+7))

### FIXED CODE ###

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

for i in range(len(a)):
    b -= a[i]
    sum += a[i]*b   

print(sum%(10**9+7))
### BUGGY CODE ###

N,M=map(int,input().split())
la=list(map(int,input().split()))
#la.sort()
for i in range(M):
    la.sort()
    la[N-1]/=2
ans=0
for i in range(N):
    ans+=int(la[i])
print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
la=list(map(lambda x:-int(x),input().split()))
heapq.heapify(la)
#la.sort()
for i in range(M):
    ll=heapq.heappop(la)/2
    heapq.heappush(la,ll)
ans=0
for i in range(N):
    ans+=int(-heapq.heappop(la))
print(ans)
### BUGGY CODE ###

N = int(input())
data = list(map(int, input().split()))
for i in range(N):
    data[i] -= (i + 1)
ave = sum(data) / N
if ave > 0:
    key = int(ave + 1)
    key1 = int(ave)
else:
    key = int(ave - 1)
    key1 = int(ave)
data.sort()
sumdata = 0
sumdata1 = 0
sumdatax = 0
#for i in data:
 #   sumdata += abs(i - key)
  #  sumdata1 += abs(i - key1)
   # sumdatax += abs(i - ave)
cnt = 0
sumdataa = 0
key = data[0] - 1
for i in data:
    if key != i:
        key = i
        for j in data:
            sumdataa += abs(j - key)
        #print(sumdataa)
        if cnt == 0:
            minsum = sumdataa
        if sumdataa < minsum:
            minsum = sumdataa
    cnt += 1
    sumdataa = 0

#print(sumdatax)
#print(data)
#print(min([sumdata, sumdata1]))
print(minsum)


### FIXED CODE ###

N = int(input())
data = list(map(int, input().split()))
for i in range(N):
    data[i] -= (i + 1)
ave = sum(data) / N
if ave > 0:
    key = int(ave + 1)
    key1 = int(ave)
else:
    key = int(ave - 1)
    key1 = int(ave)
data.sort()
sumdata = 0
sumdata2 = 0
key = data[int(N / 2) - 1]
key2 = data[int(N / 2)]
for i in data:
    sumdata += abs(i - key)
    sumdata2 += abs(i - key2)

#print(sumdatax)
#print(data)
print(min([sumdata, sumdata2]))
### BUGGY CODE ###



def read_input():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))

    clist = []
    for i in range(m):
        b, c = map(int, input().split())

        clist.extend([c]*b)

    return alist, clist

def submit():
    alist, clist = read_input()

    alist.sort(reverse=False)
    clist.sort(reverse=True)

    j = 0
    result = 0
    for a in alist:
        if j >= len(clist):
            result += a
        elif a >= clist[j]:
            result += a
        else:
            result += clist[j]
            j += 1

    print(result)



if __name__ == '__main__':
    submit()


### FIXED CODE ###



def read_input():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))

    clist = []
    for i in range(m):
        b, c = map(int, input().split())
        clist.append([c, b])

    return alist, clist

def submit():
    alist, clist = read_input()

    alist.sort(reverse=False)
    clist.sort(key=lambda x: x[0], reverse=True)

    j = 0
    result = 0
    for a in alist:
        if j >= len(clist):
            result += a
        elif a >= clist[j][0]:
            result += a
        else:
            if clist[j][1] > 0:
                result += clist[j][0]
                clist[j][1] -= 1
                if clist[j][1] == 0:
                    j += 1

    print(result)



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

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

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


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#V, E, r = map(int, input().split())
#INF = V * 10001
#A = [int(i) for i in input().split()]


N = int(input())
A = [int(i) for i in input().split()]
dp = [0]*(N+1)
ans = 0
cnt = 0
minus = 0

As = list(set(A))

for i in As:
  cnt = A.count(i)
  if(cnt<2):
    dp[i] = 0
  else:
    dp[i] = combinations_count(cnt, 2)

ans = sum(dp)

#print(dp)
for i in range(N):
  temp = dp[A[i]]
  if(dp[A[i]] == 1):
    minus = temp-1
  elif(dp[A[i]] == 0):
    minus = temp
  else:
    minus = combinations_count(A.count(A[i])-1, 2)
  print(int(ans-(temp-minus)))

#print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

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


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#V, E, r = map(int, input().split())
#INF = V * 10001
#A = [int(i) for i in input().split()]


N = int(input())
A = [int(i) for i in input().split()]
dp = [0]*(N+1)
ans = 0
cnt = 0
tle = 0

As = list(set(A))
c = Counter(A)

for i in As:
  cnt = c[i]
  if(cnt<2):
    dp[i] = 0
  else:
    dp[i] = combinations_count(cnt, 2)

tle = sum(dp)

#print(dp)
for i in range(N):
  ans = tle - (c[A[i]]-1)
  if(ans < 0):
    ans = 0
  print(int(ans))

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

import collections
import copy

n = int(input())
al = [int(x) for x in input().split()]
cs_orig = collections.Counter(al)
copy_copy = copy.copy

for a in al:
    cs = copy_copy(cs_orig)
    patterns = 0
    cs[a] -= 1
    for count in cs.values():
        if count > 1:
            patterns += int(count * (count-1) / 2)

    print(patterns)


### FIXED CODE ###

import collections

n = input()
al = tuple(x for x in input().split())
aset = set(al)

# {number: count}
ccc = collections.Counter
counts_d = ccc(al)

# Count of count
v_counts = ccc(v for v in counts_d.values())

whole_patterns = sum(
    (int(k * (k - 1) / 2)) * v for k, v in v_counts.items() if k > 1
)

[print(whole_patterns - counts_d[a] + 1) for a in al]
### BUGGY CODE ###

import itertools

X, Y, Z, K = list(map(int, input().split()))
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

AB_list = [a + b for (a, b) in list(itertools.product(A_list, B_list))]
AB_list.sort(reverse=True)
ABC_list = [ab + c for (ab, c) in list(itertools.product(AB_list[:min(3000, X*Y*Z)], C_list))]
ABC_list.sort(reverse=True)
for i in range(K):
  print(ABC_list[i])


### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

from heapq import heapify, heappop, heappush, heappushpop
 
 
class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)
 
    def push(self, item):
        heappush(self.heap, item)
 
    def pop(self):
        return heappop(self.heap)
 
    def pushpop(self, item):
        return heappushpop(self.heap, item)
 
    def __call__(self):
        return self.heap
 
 
heap = []  # ヒープといっても順序を工夫したただのリスト
 
q = PriorityQueue(heap)
q.push((-(A[0] + B[0] + C[0]), 0, 0, 0))
 
considered = set()
ans = []
for k_th in range(1, K+1):
    heap_max, i, j, k = q.pop()
    ans.append(-heap_max)
    for di, dj, dk in zip([1, 0, 0], [0, 1, 0], [0, 0, 1]):
        i_new, j_new, k_new = i + di, j + dj, k + dk
        if i_new >= X or j_new >= Y or k_new >= Z:
            continue
        if (i_new, j_new, k_new) in considered:
            continue
        considered.add((i_new, j_new, k_new))
        q.push((-(A[i_new] + B[j_new] + C[k_new]), i_new, j_new, k_new))
 
 
print(*ans, sep='\n')
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(N):
    if P.count(P[i]) > P[i]:
        ans += 1
        P[i] = 0
    elif P.count(P[i]) < P[i]:
        ans += 1
print(ans)

### FIXED CODE ###

import collections
N = int(input())
P = list(map(int,input().split()))
ans = 0
P.sort()
cnt = collections.Counter(P)
for i in cnt:
    s = cnt[i]
    if s > i:
        t =  s - i
        ans += t
    elif s < i:
        ans += s
print(ans)
### BUGGY CODE ###

n = int(input())
power = 1

for x in range(1, n+1):
  power = power * x
  
print(power % (10**9+7))

### FIXED CODE ###

power = 1
x = int(input())
for a in range(1, x + 1):
  power = (power * a) % (10**9 + 7)

print(power)
### BUGGY CODE ###

import bisect
 
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
 
def sum_count(A,B,x):
    # A,B is sorted. 
    # return count(a+b < x)
    p = len(B)-1
    result = 0
    for a in A:
        while p != -1 and a + B[p] >= x:
            p -= 1
        result += p+1
    return result

		
def f(t,A,B):
    power = (1<<t)
    AA = [x&(2*power-1) for x in A]
    BB = [x&(2*power-1) for x in B]
    AA.sort()
    BB.sort()
    
    x1,x2,x3 = (sum_count(AA,BB,v) for v in [power, 2*power, 3*power])
    zero_cnt = x1 + (x3-x2)
    return (N-zero_cnt)%2
  
ans = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		ans += 1<<t
 
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
 
def sum_count(A,B,x):
    # A,B is sorted. 
    # return count(a+b < x)
    p = len(B)-1
    result = 0
    for a in A:
        while p != -1 and a + B[p] >= x:
            p -= 1
        result += p+1
    return result
 
		
def f(t,A,B):
    power = (1<<t)
    AA = [x&(2*power-1) for x in A]
    BB = [x&(2*power-1) for x in B]
    AA.sort()
    BB.sort()
    
    x1,x2,x3 = (sum_count(AA,BB,v) for v in [power, 2*power, 3*power])
    zero_cnt = x1 + (x3-x2)
    return (N-zero_cnt)%2
  
ans = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		ans += 1<<t
 
print(ans)
### BUGGY CODE ###

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

def main():
    n,m = mi()
    tree = [set() for _ in range(n)]
    for i in range(m):
        s,t = mi()
        tree[s-1].add(t-1)
    dp = [0]*n
    dpl = [0]*n
    for i in range(n-1):
        dpl[i] = len(tree[i])
    for i in reversed(range(n-1)):
        for k in tree[i]:
            dp[i] += dp[k] 
        dp[i] /= dpl[i]
        dp[i] += 1
    ans = dp[0]
    
    def func(ss,tt):
        tmp = 0
        for l in tree[ss]:
            if l == tt:
                continue
            tmp += dp[l]
        tmp = tmp/(dpl[ss] -1) + 1
        if tmp > dp[ss]:
            return dp[0]
        else:
            dp[ss] = tmp
        
        for a in reversed(range(ss)):
            tmp = 0
            for b in tree[a]:
                tmp += dp[b]
            dp[a] = tmp/dpl[a] + 1
        
        return dp[0]
    
    for i in range(n-1):
        if len(tree[i]) == 1:
            continue
        for k in tree[i]:
            ans = min(ans,func(i,k))
    print(ans)

main()

### FIXED CODE ###

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

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp[l]
    tmp = tmp/(len(tree[ss])-1) + 1
    if tmp > dp[ss]:
        return dp[0]
    else:
        dp[ss] = tmp
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp[b]
        dp[a] = tmp/len(tree[a]) + 1
    
    return dp[0]

for i in range(n-1):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)
### BUGGY CODE ###

n = int(input())
data = [int(x) for x in input().split()]
data_elements = list(set(data))
data_dict = {}

# ボールに書かれた整数を集計する
for x in data_elements:
    data_dict[x] = data.count(x)

for k in range(n):
    data_dict_copy = data_dict.copy()
    # k番目のボールの個数を減らす
    data_dict_copy[data[k]] = data_dict_copy[data[k]] - 1

    answer = 0
    for x in data_dict_copy.values():
        answer += int(x*(x-1)/2)

    print(answer)

### FIXED CODE ###

n = int(input())
data = [int(x) for x in input().split()]
cnt = [0]*(n+1)

# ボールに書かれた整数を集計する
for x in data:
    cnt[x] += 1

total = int(sum([x*(x-1)/2 for x in cnt]))

for k in range(n):
    answer = total - cnt[data[k]] + 1
    print(answer)
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = [list(input()) for i in range(N)]
ana_list = []
ana_count = []
count = 0

for i in range(N):
    tmp = Counter(S[i])
    if tmp in ana_list:
        count += ana_count[ana_list.index(tmp)]
        ana_count[ana_list.index(tmp)] += 1
    else:
        ana_list.append(Counter(S[i]))
        ana_count.append(1)

print(count)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = list(sorted([sorted(input()) for i in range(N)]))
mini_count = 0
count = 0
tmp = S[0]

for i in range(1, N):
    if tmp == S[i]:
        mini_count += 1
        count += mini_count
    else:
        tmp = S[i]
        mini_count = 0

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

n = int(input())
a = list(int(i) for i in input().split())

for i in range(1, n + 1):
    print(a.count(i))


### FIXED CODE ###


n = int(input())
a = list(int(i) for i in input().split())
lst = [0] * (n + 1)

for i in a:
    lst[i] += 1

for i in range(1, n + 1):
    print(lst[i])
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
for q in range(Q):
  cnt = 0
  l,r = map(int, input().split())
  Sq = S[l-1:r]
  for i in range(r-l):
    if Sq[i:i+2] == 'AC':
      cnt += 1
  print(cnt)

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
AC_cum = [0]
for i in range(N-1):
  if S[i:i+2] == 'AC':
    AC_cum.append(AC_cum[-1]+1)
  else:
    AC_cum.append(AC_cum[-1])
for q in range(Q):
  l,r = map(int, input().split())
  print(AC_cum[r-1]-AC_cum[l-1])
### BUGGY CODE ###

N = int(input())

div = [0 for _ in range(10**7+5)];

for i in range(1,10**7+1):
    j = 1
    while i * j <= N:
        div[i * j] += 1
        j += 1

ans = 0

for i in range(1,N+1):
    ans += div[i] * i
print(ans)


### FIXED CODE ###

N = int(input())

div = [0 for _ in range(10**7+5)];

for i in range(1,10**7+1):
    j = 1
    while i * j <= N:
        div[i * j] += 1
        j += 1

ans = 0

for i in range(1,N+1):
    ans += div[i] * i
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
A = [0]*(N+1)
count = 0
for i in range(1,N):
    A[1] = int(S[-1])
    A[i+1] = (int(A[i])+int(S[-i-1])*10**i%2019)%2019  
    if A[i+1] in A[0:i+1]:
        a = A[0:i+1].count(A[i+1])
        count += a    
        
print(count)

### FIXED CODE ###

#数字列の逆順をSにいれる
S = input()[::-1]
#各modの値を数えるためのリスト
counts = [0]*2019
#mod==0になったら1つだけでも2019の倍数になっているので初めから＋１しておく
counts[0] = 1
#numはSの各桁の数字、dは桁数（1の位、10の位、、）
num,d = 0,1
for i in S:
    num += int(i)*d
    num %= 2019
    d *= 10
    #ここがポイント。かける桁数の値も先にmodを計算してからかけると計算量が減らせる。
    d %= 2019
    counts[num] += 1

ans = 0
for i in counts:
    ans += i*(i-1)//2

print(ans)