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

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

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

step = max(A)
X = step // 2
while X <= M:
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        cnt = X // LCM + (M - X) // LCM + 1
        print(cnt)
        exit()
    X += step
print(0)

### FIXED CODE ###

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

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

step = max(A)
X = step // 2
while X <= M:
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        cnt = X // LCM + (M - X) // LCM + 1
        print(cnt)
        exit()
    X += step
print(0)
### BUGGY CODE ###

INF = 10**9
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
dp = [[INF for _ in range(51)] for _ in range(1<<N)]
dp[0][0] = 0
for S in range(1 << N):
  j = bin(S).count("1")
  c = 0
  for i in range(N):
    if not (S & 1<<i):
      if (i - j) % 2 == 0:
        k = A[i]
      else:
        k = B[i]
      for l in range(k+1):
        dp[S|1<<i][k] = min(dp[S|1<<i][k],dp[S][l]+c)
      c += 1
ans = min(dp[-1])
print(-1 if ans == INF else ans)



### FIXED CODE ###

INF = 10**9
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
dp = [[INF for _ in range(51)] for _ in range(1<<N)]
dp[0][0] = 0
for S in range(1 << N):
  j = bin(S).count("1")
  c = 0
  for i in range(N):
    if not (S & 1<<i):
      if (i - j) % 2 == 0:
        k = A[i]
      else:
        k = B[i]
      for l in range(k+1):
        dp[S|1<<i][k] = min(dp[S|1<<i][k],dp[S][l]+c)
      c += 1
ans = min(dp[-1])
print(-1 if ans == INF else ans)
### BUGGY CODE ###

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

maxim = max(a)
minim = min(a)

while(maxim>minim*2 and m>=1):
    lmax=-1
    maxid=-1
    for i in range(n):
        if(lmax<a[i]):
            lmax=a[i]
            maxid=i
    maxim=lmax
    if(maxim<=minim*2):
        break
    a[maxid] = a[maxid]//2
    m-=1
    if(a[maxid]<minim):
        minim=a[maxid]
        
a.sort()
aa=a
a=[aa[n-1-i] for i in range(n)]
#print(a)

if(m>=1):
    for i in range(m):
        a[i%n] = a[i%n]//2
    

#print(a)
print(sum(a))

### FIXED CODE ###

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

b=[]

for i in range(n):
    for j in range(1+math.floor(math.log(a[i]+0.1)/math.log(2))):
        b.append(a[i]//(2**j)-a[i]//(2**(j+1)))
        
b.sort()
bb=b
b=[bb[len(b)-1-i] for i in range(len(bb))]


print(sum(a)-sum(b[0:m]))
### BUGGY CODE ###

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

ans =[]
for s in S:
  if s not in ans:
    ans.append(s)
print(len(ans))

### FIXED CODE ###

N = int(input())
ans = set([input() for n in range(N)])
print(len(ans))
### BUGGY CODE ###

S = input()
Q = int(input())
S = list(S)

A = []
B = []
count = 0

for i in range(Q):
    k = input()
    if k == "1":
        count += 1
    else:
        if (int(k[2]) + count) % 2 == 1:
            A = A + [k[4]]
        else:
            B = B + [k[4]]

if count % 2 == 0:
    A.reverse()
    S = A + S + B
else:
    B.reverse()
    S.reverse()
    S = B + S + A

print(*S, sep="")

### FIXED CODE ###

S = input()
Q = int(input())
 
A = ""
B = ""
count = 0

Que = []
ope = []

def rev(s):
    re = ""
    for i in range(len(s)):
        re = re + s[len(s) - 1 - i]
    return re
 
for i in range(Q):
    k = input()
    if k == "1":
        count += 1
        Que.append("1")
        ope.append("0")
    else:
        Que.append("2")
        ope.append([k[2],k[4]])
 
cou = 0
 
if count % 2 == 0:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = ope[i][1] + A
            else:
                B = B + ope[i][1]
else:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = A + ope[i][1]
            else:
                B = ope[i][1] + B
 
if count % 2 == 0:
    S = A + S + B
else:
    S = rev(S)
    S = B + S + A
 
print(S)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd

N, X, D = map(int, read().split())

if D == 0:
    if X == 0:
        print(1)
    else:
        print(N+1)
    exit()

g = gcd(X, D)
X //= g; D //= g
if D < 0:
    X, D = -X, -D

def F(d):
    event = []
    for n in range(d, N+1, D):
        
        low = X * n // D + n * (n-1) // 2 # 右の項は総和の式から
        high = X * n // D + n * (N+N-n-1) // 2
        event.append((low, 0))
        event.append((high, 1))
    event.sort()
    overlap = 0
    cnt = 0
    for x, t in event:
        if not t:
            if not overlap:
                left_end = x
            overlap += 1
        else:
            overlap -= 1
            if not overlap:
                cnt += x - left_end + 1
    return cnt
#min(D,N+1)
answer = sum(F(d) for d in range(D))
print(answer)



### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd

N, X, D = map(int, read().split())

if D == 0:
    if X == 0:
        print(1)
    else:
        print(N+1)
    exit()

g = gcd(X, D)
X //= g; D //= g
if D < 0:
    X, D = -X, -D

def F(d):
    event = []
    for n in range(d, N+1, D):
        
        low = X * n // D + n * (n-1) // 2 # 右の項は総和の式から
        high = X * n // D + n * (N+N-n-1) // 2
        event.append((low, 0))
        event.append((high, 1))
    event.sort()
    overlap = 0
    cnt = 0
    for x, t in event:
        if not t:
            if not overlap:
                left_end = x
            overlap += 1
        else:
            overlap -= 1
            if not overlap:
                cnt += x - left_end + 1
    return cnt

answer = sum(F(d) for d in range(min(D,N+1)))
print(answer)
### BUGGY CODE ###

from collections import deque
import copy
import numpy as np

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])

  count = 0
  for i in range(H*W):
    nq = deque()
    while len(q) > 0:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append([x-1,y])
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append([x,y-1])
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append([x+1,y])
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append([x,y+1])
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(i)

if __name__ == "__main__":
  main()

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N):
  flag=True
  for j in range(N):
    if i!=j and A[i]%A[j]==0:
      flag=False
      break
  if flag:
    ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
ans=0
for i in A:
  if dp[i]==0:
    for j in range(i,10**6+1,i):
      dp[j]+=1
  else:
    dp[i]+=1
for i in A:
  if dp[i]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
    A[N-1]=A[N-1]//2
    if A[N-2]>A[N-1]:
        A.sort()
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=[-1*int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a=-1*heapq.heappop(A)
    a=a//2
    heapq.heappush(A,-1*a)
print(-1*sum(A))
### BUGGY CODE ###


class UnionFindByRank():
    def __init__(self, n):
        self.number = n
        self.parents = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            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.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 全ての要素の親を求める
    def calc_parents(self):
        self.parents = [self.find(i) for i in self.parents]

    # 根を出力する
    def roots(self):
        self.calc_parents()
        return list(set(self.parents))

    # rootを親として持つ
    def groupcounts(self, root):
        return self.parents.count(root)


N, M = map(int, input().split())
uf = UnionFindByRank(N)

for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

groups = uf.roots()
counts = [uf.groupcounts(group) for group in groups]
print(max(counts))


### FIXED CODE ###

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 = map(int, input().split())

uf = UnionFind(n)

for i in range(m):
    a,b = map(int, input().split())
    uf.union(a-1, b-1)
ans = 0
roots = uf.roots()
cnt = []
for r in roots:
    cnt.append(uf.size(r))
cnt.sort(reverse=True)
ans = cnt[0]
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
Authority = [list(map(int, input().split())) for _ in range(m)]
cards = set(range(1, n + 1))

for i in range(m):
    gate = set(range(Authority[i][0], Authority[i][1] + 1))
    cards &= gate
print(len(cards))


### FIXED CODE ###

n, m = map(int, input().split())
Authority = [list(map(int, input().split())) for _ in range(m)]
cards = list(range(1, n + 2))
l_list = []
r_list = []
for i in range(m):
    l_list.append(Authority[i][0])
    r_list.append(Authority[i][1])
        
print(len(cards[max(l_list):min(r_list) + 1]))
### BUGGY CODE ###

def waru(a,b):
    if a/b==1:
        return 2
    elif b%a==0:
        return 0
    else:
        return 1

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

a.sort()
ad=[1]*n

for i in range(n-1):
    for j in range(i+1,n):
        wk=waru(a[i],a[j])
        if wk==2:
            ad[i]=0
            ad[j]=0
        else:            
            ad[j]=min(ad[j],wk)

print(sum(ad))

### FIXED CODE ###

import numpy as np

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

amax=max(a)+1
ah=[0]*amax

for i in a:
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(i, j, k)
            
print(ans)

### FIXED CODE ###

import math
from functools import reduce

K = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(i, j, k)
            
print(ans)
### BUGGY CODE ###

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

def check(L):
  for i in range(N - (L * 2) + 1):
    if S.rindex(S[i:i+L]) >= i+L:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

### FIXED CODE ###

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

def check(L):
  a = set()
  for i in range(N - (L * 2) + 1):
    a.add(S[i:i+L])
    if S[i+L:i+L+L] in a:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)
### BUGGY CODE ###

import collections

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]

for x in range(k):
    b = []
    for i,j in enumerate(a):
        b.extend(range(max(i-j,0),min(i+j+1,n)))
    a = collections.Counter(b).values()
    if len(b) == n*n:
        break
    
print(" ".join([str(x) for x in a]))

### FIXED CODE ###

import math
import numpy as np

n,k=(int(x) for x in input().split())
a = [int(x) for x in input().split()]


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))
### BUGGY CODE ###

# ?´???°?????°?????¨?????????????????°??????

import sys
import math

prim_no = {2: True}                    # ????????°????´???°??§??????????????????????????????

def is_prime(no):
    if no == 2:
        return True
    
    if no % 2 == 0:
        return False

    if prim_no.get(no) is not None:
        return prim_no.get(no)

    max_check = int(math.sqrt(no))
    for i in range(3, max_check+1, 2):
        if no % i == 0:
            prim_no[no] = False
            return False

    prim_no[no] = True
    return True

def main():
    while True:
        num = sys.stdin.readline()
        if num is None or num.strip() == '':
            break

        num = int(num.strip())
        if num == 1:
            cnt = 0
        else:
            cnt = 0
            for i in range(3, num + 1, 2):
                if is_prime(i):
                    cnt += 1
            cnt += 1

        print(cnt)

if __name__ == '__main__':
    main()
    #print(prim_no)

### FIXED CODE ###

# ?´???°?????°?????¨?????????????????°??????

import sys
import math

prim_no = {2: True}                    # ????????°????´???°??§??????????????????????????????

def is_prime(no):
    if no == 2 or no == 1:
        return True
    
    if no % 2 == 0:
        return False

    if prim_no.get(no) is not None:
        return prim_no.get(no)

    max_check = int(math.sqrt(no))
    for i in range(3, max_check+1, 2):
        if no % i == 0:
            prim_no[no] = False
            return False

    prim_no[no] = True
    return True

def main():
    prim_vals = {}                         # ????????°?????§????´???°????????°
    num_data = []                          # ?????????????????????
    
    while True:
        num = sys.stdin.readline()
        if num is None or num.strip() == '':
            break

        num = int(num.strip())
        num_data.append(num)

    sorted_num_data = sorted(num_data)
    prim_num = {}
    
    for num in sorted_num_data:
        if prim_vals.get(num) is not None:
            cnt = prim_vals.get(num)
        else:
            if num == 1:
                cnt = 0
            else:
                cnt = 0

                if num % 2 == 0:
                    start_num = num -1
                else:
                    start_num = num
                    
                for i in range(start_num, 0, -2):
                    if prim_vals.get(i) is not None:
                        cnt += prim_vals.get(i)
                        break
                    
                    if is_prime(i):
                        cnt += 1
                        
                prim_vals[num] = cnt # ????????°?????§????´???°????????°????????????
        prim_num[num] = cnt

    for num in num_data:
        print(prim_num[num])

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

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

ans = [0]*(n)

for i in range(n):
  for j in range(n):
    if i == j:
      continue
    if ans[i] == 1 or ans[j] == 1:
      continue
    if a[i] % a[j] == 0:
      ans[i] = 1
    if a[j] % a[i] == 0:
      ans[j] = 1
print(n - sum(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
dp = [0]*(ma+1)

for i in sorted(a):
  if 1 <= dp[i]:
    dp[i] += 1
    continue

  for j in range(1, ma//i + 1):
    dp[j * i] += 1

ans=0
for i in a:
  if dp[i] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
qs = [list(map(int, input().split())) for _ in range(Q)]
for q in qs:
    count = 0
    string = S[q[0]-1:q[1]]
    for i in range(q[1]-q[0]):
        if string[i] == 'A' and string[i+1] == 'C':
            count += 1
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
S = list(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
cnt = [0]*N
is_a = False
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    cnt[i+1] = 1
for i in range(1, N):
  cnt[i] += cnt[i-1]

for l, r in lr:
  l -= 1
  r -= 1
  print(cnt[r]-cnt[l])
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)

### FIXED CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

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

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N+1):
    for g in range(N+1):
        blue = N - R*r - G*g
        if blue >= 0 and blue % B == 0:
            ans += 1


print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N+1):
    for g in range(N+1):
        blue = N - R*r - G*g
        if blue >= 0 and blue % B == 0:
            ans += 1


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

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]
h, w = map(int,input().split())
grid = np.array([list(input()) for _ in range(h)])

large_grid = np.array([["." for _ in range(w+2)] for _ in range(h+2)])
goal_grid = [["#" for _ in range(w)] for _ in range(h)]
cnt = 0

for i in range(1000):
    if (grid == goal_grid).all():
        print(cnt)
        break
    for row in range(h):
        for col in range(w):
            if grid[row][col] == "#":
                large_grid[row][col+1] = "#"
                large_grid[row+2][col+1] = "#"
                large_grid[row+1][col+1] = "#"
                large_grid[row+1][col+2] = "#"
                large_grid[row+1][col] = "#"

    grid3 = large_grid[1:h+1, 1:w+1]
    #grid = grid3#参照元とかの問題でバグる
    grid = np.copy(grid3)
    cnt +=1

#     grid = grid2
#     print(grid2)
#     print(grid)








### FIXED CODE ###

from collections import deque
H, W = map(int,input().split())
grid = [list(input()) for _ in range(H)]


d = [[-1]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


que = deque()
for x in range(W):
    for y in range(H):
        if grid[y][x] == '#':
            d[y][x] = 0
            que.append([x,y])

while len(que) != 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        #print(nx,ny)
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == -1:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1

# print(d)
# print(d[H-1][W-1])
res = 0
for x in range(W):
    for y in range(H):
        res = max(res,d[y][x])
print(res)
### BUGGY CODE ###

a = input()
while (int(a) != 0):
    remain = [0for i in range(2019)]
    remain[int(a[0])] = remain[int(a[0])] + 1  ##V0
    n = len(a)
    cnt = 0
    for i in range(1,n):
        copy = remain[:]
        remain = [0for i in range(2019)]
        a_i = int(a[i])
        if (a_i != 0):
            for k in range(2019):
                rem = (k*10 + a_i)%2019
                remain[rem] += copy[k]
            remain[a_i] += 1
        elif (a_i == 0):
            for k in range(2019):
                rem = (k*10 + a_i)%2019
                remain[rem] += copy[k]
        cnt += remain[0]
    print(cnt)
    exit(0)

### FIXED CODE ###


"""
：余りの等しい物をカウントし、その累積和
：Aの余りとBの余り(mod 2019)が等しい場合
　A-Bは2019の倍数である
：計算量を抑えるため各項と１０の指数乗は分けて計算する
：
"""

import sys
input=sys.stdin.readline
s = input()[:-1][::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0

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

print(ans) # 答えの出力
### BUGGY CODE ###

# C - Attack Survival

N, K, Q = map(int, input().split())
P = [K] * N
for _ in range(Q):
    P = [p - 1 for p in P]
    i = int(input()) - 1
    P[i] += 1

for p in P:
    if 0 < p:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# C - Attack Survival

N, K, Q = map(int, input().split())
P = [0] * N
for _ in range(Q):
    P[int(input()) - 1] += 1

for p in P:
    if 0 < K - Q + p:
        print('Yes')
    else:
        print('No')