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

n =int(input())
s = list(map(int,input().split()))
i = 1
while i <= n:
     print(s.count(i))
     i += 1

### FIXED CODE ###

n =int(input())
s = list(map(int,input().split()))
l =[0]*n
i = 0
while i < n-1 :
     l[s[i]-1] += 1
     i += 1
for _ in range(n):
     print(l[_])
### BUGGY CODE ###

k,s = map(int,input().split())

count = 0

for i in range(k + 1):
    for j in range(k + 1):
        for t in range(k + 1):
            if i + j + t == s:
                count += 1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())

count = 0

for x in range(k + 1):
    for y in range(k + 1):
        if 0 <= s - x - y <= k:
            count += 1
print(count)
### BUGGY CODE ###

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

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j: continue
            
            if a[i] % a[j] == 0:
                break
        else:
            ans += 1

    print(ans)

resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    max_a = max(A)
    m = set()
    checked = set()
    duplicated = set()

    for a in A:
        if a in checked:
            duplicated.add(a)
            continue

        i = 2
        while a*i <= max_a:
            m.add(a*i)
            i += 1

        checked.add(a)

    ans = 0
    for a in A:
        if a in duplicated: continue

        if a not in m:
            ans += 1
    
    print(ans)
 
resolve()
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
cd.sort(reverse=True)

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[i].append(j)

ans = []
temp= [[0, {-1}]]

while temp:
    q = temp.pop()
    if q[0] == N:
        ans.append(len(q[1])-1)
    else:
        for i in g[q[0]]:
            if not i in q[1]:
                s = q[1] | {i}
                temp.append([q[0]+1, s])
        temp.append([q[0]+1, q[1]])            
print(max(ans))

### FIXED CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
cd.sort()

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[j].append([pab[1],i])
        
ans = 0
s = set()

for gg in g:
    gg.sort(reverse=True)
    for ggg in gg:
        if ggg[1] in s:continue
        else:
            ans += 1
            s.add(ggg[1])
            break
print(ans)
### BUGGY CODE ###

N = int(input())
list_S = [input() for i in range(N) ]
list_S.sort()
list_a = []
a = 0
while a < N :
    list_a.append(list_S.count(list_S[a]))
    a += list_S.count(list_S[a])
newlist_a = sorted(list_a,reverse=True)
n = newlist_a.count(newlist_a[0])
ans = ""
if n == 1:
    t = 0
    for i in range(list_a.index(newlist_a[0])):
        t += list_a[i]
    ans = list_S[t+1]
else:
    if newlist_a[0]==1:
        for i in range(len(list_S)):
            ans += list_S[i]
            ans += "\n"
    else:            
        list_t = []
        for i,x in enumerate(list_a):
            if x == newlist_a[0]:
                list_t.append(sum(list_a[0:i]))
        for i in range(len(list_t)):
            ans += list_S[list_t[i]]
            ans += "\n"
print(ans)

### FIXED CODE ###

import collections

N = int(input())
S = [input() for i in range(N)]
c =collections.Counter(S)
C = c.most_common()
list_C = []
for i in range(len(c)):
    list_C.append(C[i][1])
m = 1
for i in range(len(list_C)-1):
    if list_C[i]==list_C[i+1]:
        m += 1
    else:
        break
ans= []
for i in range(m):
    ans.append(C[i][0])
ans = sorted(ans)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 
        
    print(ans)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019
    print(ans)

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

s = input()
Q = int(input())
q = []
f = []
c = []

for _ in range(Q):
    tmp = list(map(str,input().split()))
    if len(tmp) == 1:
        q.append(int(tmp[0]))
        f.append(0)
        c.append('')
    else:
        q.append(int(tmp[0]))
        f.append(int(tmp[1]))
        c.append(tmp[2])
s2 = s[::-1]
for i in range(Q):
    if q[i] == 1:
        tmp = s
        s = s2
        s2 = tmp
    else:
        if f[i] == 1:
            s = c[i] + s
            s2 = s2 + c[i]
        else:
            s = s + c[i]
            s2 = c[i] + s2

print(s)


### FIXED CODE ###

from collections import deque

s = list(input())
s2 = deque(list(reversed(s)))
s = deque(s)
Q = int(input())
q = []
f = []
c = []
count = 0

for _ in range(Q):
    tmp = list(map(str,input().split()))
    if len(tmp) == 1:
        count += 1
        q.append(int(tmp[0]))
        f.append(0)
        c.append('')
    else:
        q.append(int(tmp[0]))
        f.append(int(tmp[1]))
        c.append(tmp[2])


for i in range(Q):
    if q[i] == 1:
        tmp = s
        s = s2
        s2 = tmp
    else:
        if f[i] == 1:
            s.appendleft(c[i])
            s2.append(c[i])
        else:
            s.append(c[i])
            s2.appendleft(c[i])

for i in range(len(s)):
    print(s.popleft(),end="")
print("")
### BUGGY CODE ###

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

C.sort(reverse=True)

ab = [a+b for a in A for b in B]
ab.sort(reverse=True)

ans = [x+c for x in ab[:K] for c in C]
ans.sort(reverse=True)
print('\n'.join(map(str, ans[:K])))


### FIXED CODE ###

X, Y, X, K = 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)

ab = [a+b for a in A for b in B]
ab.sort(reverse=True)

ans = [x+c for x in ab[:K] for c in C]
ans.sort(reverse=True)
print('\n'.join(list(map(str, ans[:K]))))
### BUGGY CODE ###

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

ans = 0
for j in range(N):
  for k in range(j+1,N):
    if len(set(S[j])^set(S[k])) == 0:
      S[j].sort()
      S[k].sort()
      if (''.join(S[j]) == ''.join(S[k])):
        ans += 1
           
           
print(ans)
           

### FIXED CODE ###

from operator import itemgetter
N = int(input())
S = [list(input()) for i in range(N)]

for l in range(N):
  S[l].sort()
  S[l] = ''.join(S[l]) 

S.sort()

X = []
p = 1

for j in range(N-1):
  if S[j] == S[j+1]:
    p +=1
  else:
    X.append(p)
    p = 1
X.append(p)


def comb(n):
  if n == 2: return 1
  else:
    return int(n*(n-1)/2)

ans = 0

for k in range(len(X)):
  ans += comb(X[k])

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

import bisect
import sys
from itertools import accumulate
input = sys.stdin.readline
def hsnum(ls,x,n):
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 2*10**5+2
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx,n) < m:
        rx = mx
    elif hsnum(a,mx,n) > m:
        if hsnum(a,mx+1,n) < m:
            error = hsnum(a,mx,n)-m
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
ans = 0
for i in range(n):
    rema = lx - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]+suma[n]-suma[j]
print(ans-error*lx)

### FIXED CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx -= 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = min(a)
l = []
for i in range(n):
  if a[i] < 2*10**5-m:
    l.append((i, a[i]))
count = 0

for i in range(len(l)-1):
  for j in range(i+1, len(l)):
    if l[j][0]-l[i][0] == l[j][1]+l[i][1]:
      count += 1

print(count)

### FIXED CODE ###

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

lr = [[0,0] for i in range(n)]

for i in range(n):
  l = i+a[i]
  if l < n:
    lr[l][0] += 1
  r = i-a[i]
  if r > 0:
    lr[r][1] += 1
count = 0
for i in range(n):
  count += lr[i][0] * lr[i][1]
print(count)
### BUGGY CODE ###

import math
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

ans = 1
for i in range(N):
    g = reduce(math.gcd,A[:i]+A[i+1:])
    ans = max(ans,g)
print(ans)

### FIXED CODE ###

import math
from collections import deque
N = int(input())
A = list(map(int,input().split()))

M = 0
L = deque([0])
R = deque([0])
for i in range(1,N+1):
    L.append(math.gcd(L[-1],A[i-1]))
    R.appendleft(math.gcd(R[0],A[N-i]))
for j in range(N):
    m = math.gcd(L[j],R[j+1])
    M = max(M,m)
print(M)
### BUGGY CODE ###



N = int(input())
S = input()
S = S[::-1]

cnt = S.count('B')*S.count('G')*S.count('R')
# for i in range(1,N-1):
#     for j in range(i+1,N):
#         if S[i-1] != S[j-1]:
#             for k in range(j+1,N+1):
#                 if S[i-1]!=S[k-1] and S[j-1]!=S[k-1] and j-i!=k-j:
#                     cnt += 1
for i in range(N-2):
    for j in range(i,N-1):
        k = 2*j-i
        if k>j and k<=N-1:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] :
                cnt -= 1


print(cnt)

### FIXED CODE ###



N = int(input())
S = input()
S = S[::-1]

cnt = S.count('B')*S.count('G')*S.count('R')

for i in range(N-2):
    for j in range(i,N-1):
        k = 2*j-i
        if  k<=N-1:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] :
                cnt -= 1


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

x,y,z,k=map(int,input().split())
listx = [int(i) for i in input().split()]
listy = [int(i) for i in input().split()]
listz = [int(i) for i in input().split()]

import numpy as np
listxy = np.zeros([x*y,],dtype=np.int)
c = 0
for i in range(0,x):
    for j in range(0,y):
        listxy[c] = listx[i]+listy[j]
        c+=1

listxy.sort()
#print(listxy)
if x*y>k:
    listxy=listxy[-k:]
    listxyz =np.zeros([k*z,],dtype=np.int)
    c = 0
    for i in range(0,k):
        for j in range(0,z):
            listxyz[c] = listxy[i]+listz[j]
            c+=1
else:
    listxyz =np.zeros([x*y*z,],dtype=np.int)
    c = 0
    for i in range(0,x*y):
        for j in range(0,z):
            listxyz[c] = listxy[i]+listz[j]
            c+=1

listxyz.sort()
if len(listxyz)>k:
    listxyz=listxyz[-k:]
for i in range(0,k):
    print(listxyz[-(i+1)])

### FIXED CODE ###

X,Y,Z,K = 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)
A = A[0:K]
B.sort(reverse=True)
B = B[0:K]
AB = [a+b for a in A for b in B]

AB.sort(reverse=True)

AB = AB[0:K]

C.sort(reverse=True)
C=C[0:K]
ABC = [ab+c for ab in AB for c in C]

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

n=int(input())
def warshall_floyd(d,k):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d[k-1]

graph = [[float("inf") for x in range(n)] for _ in range(n)]

for i in range(n-1):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

for i in range(n):
    graph[i][i] = 0
q,k = map(int,input().split())
G = warshall_floyd(graph,k)
ans = []

for i in range(q):
    x,y = map(int,input().split())
    ans.append(G[x-1] + G[y-1])

print(*ans , sep="\n")

### FIXED CODE ###

from collections import deque

def f(k,edge,n):
    root = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = edge[i][0],edge[i][1],edge[i][2]
        root[a-1].append([b-1,c])
        root[b-1].append([a-1,c])
    
    que = deque()
    for l in root[k]:
        que.append(l)
    
    dist = [float("inf")]*n
    dist[k] = 0
    visited = [False]*n
    que = deque([k])

    while que:
        pos = que.popleft()
        if not visited[pos]:
            visited[pos] = True
        for x,y in root[pos]:
            if not visited[x]:
                dist[x] = dist[pos] + y
                visited[x] = True
                que.append(x)
    return dist

n = int(input())
edge = [list(map(int,input().split())) for _ in range(n-1)]

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

ans = []
d = f(k-1,edge,n)
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1] + d[y-1])

print(*ans , sep = "\n")
### BUGGY CODE ###

n = int(input())

a = [0 for i in range(n)]
a = [int(s) for s in input().split()]
res = 0

dig_0 = [0 for i in range(60)]
dig_1 = [0 for i in range(60)]

for i in range(n):
    #print("----")
    for j in range(60):
        #print(bin(a[i]>>j))
        s = bin(a[i]>>j)[-1]
        if(s == "1"):
            dig_1[j] += 1
        else:
            dig_0[j] += 1

#print(dig_1)
for i in range(60):
    #print(dig_0[i],dig_1[i])
    res += dig_0[i]*dig_1[i]*2**i
    #print(res)
md = 10**9 + 7
print(res%md)


### FIXED CODE ###

n = int(input())

a = [0 for i in range(n)]
a = [int(s) for s in input().split()]
res = 0

dig_0 = [0 for i in range(60)]
dig_1 = [0 for i in range(60)]

for i in range(n):
    #print("----")
    for j in range(60):
        #print(bin(a[i]>>j))
        s = (a[i]>>j)%2
        if(s == 1):
            dig_1[j] += 1
        else:
            dig_0[j] += 1

#print((3>>1)%2)
for i in range(60):
    #print(dig_0[i],dig_1[i])
    res += dig_0[i]*dig_1[i]*2**i
    #print(res)
md = 10**9 + 7
print(res%md)
### BUGGY CODE ###

INF = float('inf')
N, M = map(int, input().split())
dist = [0] + [INF] * (N-1)
abc = []

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append((a, b, -c))
    
for i in range(N-1):
    for a, b, c in abc:
        dist[b-1] = min(dist[b-1], dist[a-1]+c)
        
ans = dist[-1]
negative = [False] * N

for i in range(N):
    for a, b, c in abc:
        if dist[b-1] > dist[a-1]+c:
            dist[b-1] = dist[a-1]+c
            negative[b-1] = True
        if negative[a-1]:
            negative[b-1] = True
        
if negative[-1]:
    print('inf')
else:
    print(-ans)

### FIXED CODE ###

def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = map(int, input().split())
        abc.append((a, b, -c))
        
    for i in range(N-1):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            dist[b-1] = min(dist[b-1], dist[a-1]+c)
            
    ans = dist[-1]
    negative = [False] * N
    
    for i in range(N):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            elif dist[b-1] > dist[a-1]+c:
                dist[b-1] = dist[a-1]+c
                negative[b-1] = True
            if negative[a-1]:
                negative[b-1] = True
            
    if negative[-1]:
        print('inf')
    else:
        print(-ans)

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

import numpy as np
import collections

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

# N = 5
# A = [1, 1, 2, 1, 2]

for i in range(N):
    # i = 2
    A_sub = A.copy()
    # A_sub.pop(i)

    # A_sub = np.array(A_sub)

    ans = 0
    # u, counts = np.unique(A_sub, return_counts=True)
    c = collections.Counter(A_sub)
    for j in c:
        # val = uni_vals[0]
        n = c[j]
        if j == A[i]:
            n -= 1
        ans += (n*(n-1))/2

    print(int(ans))


### FIXED CODE ###

from collections import defaultdict, Counter

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

d = defaultdict(int)
for a in A:
    d[a] += 1

all = 0
for val in d.values():
    all += val * (val - 1) / 2

all = int(all)
val_cnt = Counter(A)
for a in A:
    print(all - (val_cnt[a] - 1))
### BUGGY CODE ###

from collections import deque
from copy import deepcopy

N, M, K = map(int, input().split())
SNS = [[0 for _ in range(N+1)] for __ in range(N+1)]
Follow = [deque() for __ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
  Follow[a].append(b)
  Follow[b].append(a)
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1

Chains = []
seen = [False]*(N+1)
i = 1
while i <= N:
  if not seen[i]:
    seen[i] = True
    chain = deque()
    q = deque(Follow[i])
    memo = [False]*(N+1)
    while q:
      j = q.pop()
      if not memo[j]:
        memo[j] = True
        seen[j] = True
        chain.append(j)
        q += Follow[j]
    Chains.append(deepcopy(chain))
  i += 1
ans = [0] * (N+1)

for chain in Chains:
  l = len(chain)
  for hito in chain:
    n = 0
    for aite in chain:
      n += 0 if SNS[hito][aite] == 0 else 1
    ans[hito] = l - n -1
print(" ".join([str(a) for a in ans[1:]]))


### FIXED CODE ###

from collections import deque
from copy import deepcopy

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = map(int, input().split())
UF = UnionFind(N+1)
direct_connect = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  UF.union(a, b)
  direct_connect[a] += 1
  direct_connect[b] += 1
for _ in range(K):
  a, b = map(int, input().split())
  if UF.same(a, b):
    direct_connect[a] += 1
    direct_connect[b] += 1
ans = ""
for i in range(1, N+1):
  ans += "%d "%(UF.size(i)-direct_connect[i]-1)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = []
for i in range(1,len(A)+1,1):
    ans.append(A.index(i)+1)
print(*ans)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = [0]*N
for i,a in enumerate(A):
    ans[a-1] = i+1
print(*ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache

T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    @lru_cache(maxsize=10**7)
    def rec(i,x):
        if i==N:
            return 1 if x>0 else 0
        if S[i]=='0':
            a = rec(i+1,x)
            if a == 0: ret = 0
            else:
                b = rec(i+1,x^A[i])
                ret = b
        else:
            a = rec(i+1,x)
            if a == 1: ret = 1
            else:
                b = rec(i+1,x^A[i])
                ret = b
        return ret
    print(rec(0,0))

### FIXED CODE ###

def gauss_jordan(bs):
    rank = 0
    pivot_cols = []
    for col in reversed(range(61)):
        pivot = -1
        for i,row in enumerate(bs[rank:]):
            if row&(1<<col):
                pivot = rank+i
                break
        if pivot < 0: continue
        pivot_cols.append(col)
        bs[pivot],bs[rank] = bs[rank],bs[pivot]
        for i,row in enumerate(bs):
            if i != rank and row&(1<<col):
                bs[i] ^= bs[rank]
        rank += 1
    return bs

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    bs = []
    for a,s in zip(A[::-1],S[::-1]):
        x = a
        for b in bs:
            x = min(x, x^b)
        if x:
            if s=='0':
                bs.append(x)
                bs = gauss_jordan(bs)
            else:
                return 1
    return 0

T = int(input())
for _ in range(T):
    print(solve())
### BUGGY CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0

for i in range(n):
    num = num + int(s[-1-i])*(10**(i))
    tmp = num%2019
    amari[tmp]+=1

from math import factorial

ans = 0
for key,val in amari.items():
    if val>1:
        ans +=factorial(val) // factorial(2) // factorial(val - 2)

print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*pow(10,i,2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

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

n, k = map(int, input().split())
list_score = list(map(int, input().split()))

list_ans = 0

for i in range(n-k+1):
    list_sum = list_score[i:i+k]
    if sum(list_sum) >= list_ans:
        list_ans = sum(list_sum)




ans = list_ans*0.5 + 0.5*k

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
list_P = list(map(int, input().split()))
cnt = 0

for i in range(k):
    p = list_P[i]
    cnt += (1+p)/2

ans = cnt
for i in range(k, n):
    p, q = list_P[i-k], list_P[i]
    cnt -= (1+p)/2
    cnt += (1+q)/2
    ans = max(ans, cnt)

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

N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
  for w in range(W+1):  
    if w-wv[2*i] >= 0:
      dp[i+1][w] = max(dp[i+1][w], dp[i][w-wv[2*i]]+wv[2*i+1])
    dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
  for w in range(W+1):  
    if w-wv[2*i] >= 0:
      dp[i+1][w] = max(dp[i+1][w], dp[i][w-wv[2*i]]+wv[2*i+1])
    dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])
### BUGGY CODE ###

slime_number = int(input())
slime_colors = list(input())

concatable = True

while concatable:
  if slime_number == 1:
     break
  i = 0
  while i < slime_number - 1:
    concatable = False
    if slime_colors[i] == slime_colors[i + 1]:
      slime_colors = slime_colors[:i] + slime_colors[i+1:]
      concatable = True
      slime_number -= 1
    else:
      i += 1
      
print(slime_number)

### FIXED CODE ###

slime_number = int(input())
slime_colors = list(input())

last_slime = 'ほげ'
result = 0

for i in range(slime_number):
  if last_slime != slime_colors[i]:
    last_slime = slime_colors[i]
    result += 1

print(max(result, 1))