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

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

dp_l = [[0] * (k + 1) for _ in range(n + 1)]
dp_l[0][0] = 1

for i, e in enumerate(a):
    for j in range(k + 1):
        dp_l[i+1][j] += dp_l[i][j]
        nxt = min(k, j + e)
        dp_l[i+1][nxt] += dp_l[i][j]

dp_r = [[0] * (k + 1) for _ in range(n + 1)]
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    for j in range(k + 1):
        dp_r[i+1][j] += dp_r[i][j]
        nxt = min(k, j + e)
        dp_r[i+1][nxt] += dp_r[i][j]

for i in range(n + 1):
    for j in range(k, 0, -1):
        dp_r[i][j-1] += dp_r[i][j]

base = dp_l[n][k]
ans = 0
for i in range(1, n + 1):
    cnt = 0
    for j in range(k + 1):
        cnt += dp_l[i-1][j] * dp_r[n-i][k-j]
    if 2 * cnt == base:
        ans += 1

print(ans)


### FIXED CODE ###

import numpy as np


def check(x):
    dp = np.zeros(k, np.bool)
    dp[0] = True
    for e in a[:x] + a[x+1:]:
        dp[e:] |= dp[:-e]

    return dp[-a[x]:].any()


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

a.sort()

lb = -1
ub = n
while ub - lb > 1:
    m = (lb + ub) // 2
    if check(m):
        ub = m
    else:
        lb = m

print(ub)
### BUGGY CODE ###

import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    return bin(next_int).count('1')
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


#X_cnt = calc_bin_cnt(X_int)
X_cnt = X_bin.count('1')
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
### BUGGY CODE ###

n = int(input())
a= list(map(int,input().split()))
#a = list(set(a))
a.sort
ind = [1] * len(a)

for i in range(len(a)):
  for j in range(len(a))[::-1]:
    if (i != j) & (ind[i] != 0) & (ind[j] != 0) & (a[j]%a[i] == 0):
      if a[i] == a[j]:
        ind[i] = 0
      ind[j] = 0

print(sum(ind)) 


### FIXED CODE ###

from collections import Counter
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()

c = Counter(a)
a = list(set(a))
dp = [0] * (10**6 +1)

for x in a:
  t = x * 2
  while t <= 10**6:
    dp[t] = 1
    t += x

ans = 0
for x in a:
  if (c[x] == 1) & (dp[x] == 0):
    ans += 1

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

n=int(input())
ans=0
for i in range(1,n+1):
    x,y=i,(n//i)*i
    ans+=((n//i)*(x+y)//2)
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    x,y=i,(n//i)*i
    ans+=((n//i)*(x+y)//2)
print(ans)
### BUGGY CODE ###

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

S += "X"
j = 0
count = 1
change = [] if S[0] != "0" else [0]
while j < len(S)-1:
  if S[j:j+2] == "10":
    change.append(count)
    count = 0
  elif S[j:j+2] == "01":
    change.append(count)
    count = 0
    
  j += 1
  count += 1

change.append(count-1)
i = 0
max_len = 0
while i < len(change):
  max_len = max([sum(change[i:i+2*K+1]), max_len])
  i += 2
  
print(max_len)

### FIXED CODE ###

N, K = list(map(int, input().split()))
S = input()
 
S += "X"
i = 0
j = 0
max_len = 0
change = 0 if S[0] != "0" else 1
while j < len(S)-1:
  if change <= K:
    #print(i, j)
    max_len = max([j-i+1, max_len])
    if S[j:j+2] == "10":
      change += 1
    j += 1
  else:
    if S[i:i+2] == "01":
      change -= 1
    i += 1

print(max_len)
### BUGGY CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template

H,W = inputlist()
st = inputlist()
gl = inputlist()
maze = ['0']*H
for i in range(H):
    maze[i] = list(input())
table = [[10**9+7]*W for _ in range(H)]

from collections import deque
dx = [0,1,0,-1]
dy = [1,0,-1,0]

que = deque()
table[st[0]-1][st[1]-1] = 0
que.append((st[0]-1,st[1]-1,0))

while len(que) != 0:
    x,y,c = que.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and table[nx][ny] > c:
            table[nx][ny] = c
            que.append((nx,ny,c))

    for i in range(-2,3):
        for j in range(-2,3):
            if (i,j) == (0,1) or (i,j) == (1,0) or (i,j) == (0,-1) or (i,j) == (-1,0):
                continue
            nxa = x+i
            nya = y+j

            if 0 <= nxa < H and 0 <= nya < W and maze[nxa][nya] == "." and table[nxa][nya] > c+1:
                table[nxa][nya] = c+1
                que.append((nxa,nya,c+1))

if table[gl[0]-1][gl[1]-1] == 10**9+7:
    print(-1)
else:
    print(table[gl[0]-1][gl[1]-1])

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
 
for i in range(1, n+1):
    x = a.count(i)
    print(x)

### FIXED CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
cnt = collections.Counter(a)

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

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

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

jun = []
# O(2n)
def chil_pop(l,p):
    jun.append(l)
    for i in b[l]:
        if i == p:
            continue
        chil_pop(i,l)
    b[l] = p

chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x

for i in jun[1:]:
    ans[i] += ans[b[i]]

ans_str = ''
for i in range(n):
    print(ans[i],end=' ')
    # ans_str = ans_str + str(ans[i]) + ' '
# print(ans_str)


### FIXED CODE ###

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

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())
print(*sorted({*range(a, b + 1)} & ({*range(a, a + k)} | {*range(b - k + 1, b + 1)})),sep="\n")


### FIXED CODE ###

#!/usr/bin/env python3
a, b, k = map(int, input().split())
if (b - a) // 2 + 1 < k:
    print(*range(a, b + 1), sep="\n")
else:
    print(*sorted(set([*range(a, a + k)] + [*range(b - k + 1, b + 1)])),
          sep="\n")
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
K1 = min(K, len(A))

B = list(map(int, input().split()))
B.sort(reverse=True)
K2 = min(K, len(B))

C = list(map(int, input().split()))
C.sort(reverse=True)
K3 = min(K, len(C))

K12 = min(K1 * K2, K)

M1 = [0] * (K1 * K2)
k = 0
for i in range(0, K1):
    for j in range(0, K2):
        M1[k] = A[i] + B[j]
        k += 1

M1.sort(reverse=True)

M = [0] * (K12 * K3)
k = 0
for i in range(0, K12):
    for j in range(0, K3):
        M[k] = M1[i] + C[j]
        k += 1

M.sort(reverse=True)

for i in range(0, K):
    print(M[i])


### FIXED CODE ###


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

M = []
for i in range(0, X):
    for j in range(0, Y):
        for k in range(0, Z):
            if (i+1) * (j+1) * (k+1) <= K:
                M.append(A[i] + B[j] + C[k])
            else:
                break

M.sort(reverse=True)
for i in range(0, K):
    print(M[i])
### BUGGY CODE ###

N=int(input())
lst=[None]*N
for i in range(N):
    lst[i]=''.join(sorted(input()))
count=0
for el in set(lst):
    num=lst.count(el)
    count+=num*(num-1)//2
print(count)

### FIXED CODE ###

N=int(input())
lst=[None]*N
for i in range(N):
    lst[i]=''.join(sorted(input()))
count=0

import collections
dict=collections.Counter(lst)

for k, v in dict.items():
    count+=v*(v-1)//2

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

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j in magic:
                if i-j[0] < 0:
                    num = ans[i]+j[1]
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+j[1]
                    if ans[i-j[0]] > num:
                        ans[i-j[0]] = num
    return ans[0]
print(num())




### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###

N = int(input())

r = 0
for u in range(1, 10):
    for l in range(1, 10):
        r1 = 0
        r2 = 0
        for i in range(1, N + 1):
            if i % 10 == l and int(str(i)[0]) == u:
                r1 += 1
            if i % 10 == u and int(str(i)[0]) == l:
                r2 += 1
        r += r1 * r2
print(r)



### FIXED CODE ###

import math
from collections import defaultdict

N = int(input())

rr = defaultdict(lambda: 0)
for i in range(1, N + 1):
    x = int(i / (10 ** int(math.log10(i))))
    y = i % 10
    rr[(x, y)] += 1

r = 0
for u in range(1, 10):
    for l in range(1, 10):
        r += rr[(u, l)] * rr[(l, u)]
print(r)
### BUGGY CODE ###

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

import math

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

def findsame(aa):
    s = 0
    for a in aa:
        s += (len([x for x in aa if x == a]) - 1)
    return int(s / 2)

for k in range(len(aa) - 1):
    print(findsame(aa[:k] + aa[k+1:]))
print(findsame(aa[:len(aa)-1]))


### FIXED CODE ###

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

import math

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

# def findsame(aa):
#     s = 0
#     for a in aa:
#         s += (len([x for x in aa if x == a]) - 1)
#     return int(s / 2)

# for k in range(len(aa) - 1):
#     print(findsame(aa[:k] + aa[k+1:]))
# print(findsame(aa[:len(aa)-1]))

# aaa = dict()
# for a in aa:
#     if a not in aaa:
#         aaa[a] = len([x for x in aa if x == a])

# sum = 0
# for k in aaa:
#     sum += int(aaa[k] * (aaa[k] - 1) / 2)

# for a in aa:
#     print(sum - (aaa[a] - 1))

aaa = dict()
for a in aa:
    if a not in aaa:
        aaa[a] = 1
    else:
        aaa[a] += 1

sum = 0
for k in aaa:
    sum += int(aaa[k] * (aaa[k] - 1) / 2)

for a in aa:
    print(sum - (aaa[a] - 1))
### BUGGY CODE ###

# 入力は二行でそれぞれ[数値]

input_nums = int(input())
input_line = input()

result = 0

for k in range(input_nums):
    for j in range(k):
        for i in range(j):
            if(j-i == k-j):
                pass
            elif(input_line[i] != input_line[j] and input_line[i] != input_line[k] and input_line[j] != input_line[k]):
                    result = result + 1

print(result)


### FIXED CODE ###

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

ans = S.count("R")*S.count("G")*S.count("B")

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

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

from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      if x not in q and y not in q:
        q.append(x)
        q.append(y)
        a[x].popleft()
        a[y].popleft()

  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if len(a[y])==0: continue;
      if x == a[y][0] and x not in q and y not in q:
        q.append(x)
        q.append(y)
        a[x].popleft()
        a[y].popleft()

    #print(f'a={a}')
    if len(q)==0: break;


  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      exit()
  print(day)


if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      exit()
  print(day)


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

from sys import exit
from itertools import accumulate,chain
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t[i],min(accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))] for i in range(n)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

### FIXED CODE ###

import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #いや、間違ってるのここなんかーーい
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i) for i in range(n)]
a.sort(key=lambda x: -x[0])
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for x in range(n+1):
    for y in range(n+1):
        if x + y > n:
            break
        active, idx = a[x+y-1]
        if x > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x-1][y] + active * abs(idx - (x-1)))

        if y > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x][y-1] + active * abs(idx - (n-y)))

ans = 0
for x in range(n+1):
    ans = max(ans, dp[x][n-x])

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i) for i in range(n)]
a.sort(key=lambda x: -x[0])
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for x in range(n+1):
    for y in range(n+1):
        if x + y > n:
            break
        active, idx = a[x+y-1]
        if x > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x-1][y] + active * abs(idx - (x-1)))

        if y > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x][y-1] + active * abs(idx - (n-y)))

ans = 0
for x in range(n+1):
    ans = max(ans, dp[x][n-x])

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

n=int(input())
o=list(i for i in range(1,n+1))
sum=0
l=[]
for j in o:
    if j % 5 == 0:
        o.remove(j)
for p in o :
    if p%3==0:
        o.remove(p)
for k in o:
    sum+=k
print(sum)


### FIXED CODE ###

n=int(input())
l=[]
o=list(i for i in range(1,n+1))
for j in o:
    if j%5 ==0 or j%3 ==0:
        l.append(j)
print(sum(o)-sum(l))
### BUGGY CODE ###


def resolve():
    inp = input()
    orginp = inp
    while True:
        update = 0
        for i in range(len(inp)-1):
            if inp[i] != inp[i+1]:
                if len(inp) > i+1:
                    inp = inp[:i] + inp[i+2:]
                else:
                    inp = inp[:i]
                update += 1
                break
        if update == 0:
            break
    print(len(orginp)-len(inp))

resolve()

### FIXED CODE ###

def resolve():
    inp = input()

    c0 = inp.count('0')
    c1 = inp.count('1')

    print(min(c0, c1)*2)

resolve()
### BUGGY CODE ###

N = int(input())
import numpy as np
#max=int(np.sqrt(N))

for n in range(1,N+1):
    j=0
    min = 1
    max = int(np.sqrt(abs(n-2)))
    #print(max)
    for x in range(min,max):
        #print(f'max:{max}')
        for y in range(min, max):
            for z in range(min, max):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x > n:
                    break
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                    if x == y == z:
                        max=x
                        min=x
                        j += 1
                        break
                    if j==0:
                        max = z+1
                        min += 1
                        #min = x
                        #print(x, y, z)
                        #print(f'n:{n}')
                        j += 3
                    # else:
                    #     j += 3

    print(j)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1

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

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n

def unite(x, y):
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if CX < CY:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    for i in range(n):
      if clusterI[i] == CY:
        clusterI[i] = CX

for _ in range(m):
  a, b = map(int, input().split())
  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):
  a, b = map(int, input().split())
  if clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

### FIXED CODE ###

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = generateC(x)
  CY = generateC(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if generateC(a-1) == generateC(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[generateC(i)] - 1 for i in range(n)]
print(*out)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:28:26 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
dic = {}
mod = 2019
count = 0

for i in range(1,n+1):
    num = int(s[n-i:n])
    num = num%mod
    if num in dic:
        dic[num] += 1
    if num not in dic:
        dic[num] = 1

ans = 0
for fact in dic:
    ans += dic[fact]*(dic[fact]-1)//2
if 0 in dic:
    ans += dic[0]

print(ans)

### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

print(ans)