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

import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 56) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] + ord(char)) * rh.BASE % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 45) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] + ord(char)) * rh.BASE % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

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

NK = input().split()
N, K = int(NK[0]), int(NK[1])
lis_p = list(map(lambda x: int(x), input().split()))
lis_exp = list(map(lambda x: (x+1)/2, lis_p))
dp=0
for i in range(N):
    dp = max(sum(lis_exp[i:i+K]), dp)
print(dp)

### FIXED CODE ###

N, K = map(int, input().split())
lis_p = map(int, input().split())
def calc_exp(x):
    return (int(x) + 1)/2
lis_exp = list(map(calc_exp, lis_p))
dp= sum(lis_exp[0:K])
cumKsum = sum(lis_exp[0:K])
for i in range(1, N-K+1):
    cumKsum = cumKsum - lis_exp[i-1] + lis_exp[i+K-1]
    dp = max(cumKsum, dp)
print(dp)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    
    L = sorted(L)
    
    ans = 0
    for i in range(N-2):
        for j in range(N-1):
            if j > i:
                b = L[j] - L[i]
                c = L[i] + L[j]
                mi = bisect.bisect_left(L[j+1:], b)
                ma = bisect.bisect_left(L[j+1:], c)
                ans += ma - mi
    
    print(ans)
    
if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L)

    ans = 0
    for i in range(N-2):
        for j in range(N-1):
            if j > i:
                ans += bisect.bisect_left(L[j+1:], L[i] + L[j])

    print(ans)

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

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):return (int(x)%kk,int(y)%kk)
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(kk):
        for j in range(kk):
            a_t=((0,max(i-k,0),-2),(max(i-k,0),i,-1),(i,min(i+k,kk),0),(min(i+k,kk),kk,1))
            b_t=((0,max(j-k,0),-2),(max(j-k,0),j,-1),(j,min(j+k,kk),0),(min(j+k,kk),kk,1))
            a_t=[(i,j,l) for i,j,l in a_t if i!=j]
            b_t=[(i,j,l) for i,j,l in b_t if i!=j]
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append([r-1,d])
    g[r-1].append([l-1,d*(-1)])
f=[False for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if type(f[sg[0]]) == bool:
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if type(f[i]) == bool:
            if not dfs(i,1):
                return "No"
    return "Yes"

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append([r-1,d])
    g[r-1].append([l-1,d*(-1)])
f=[False for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if type(f[sg[0]]) == bool:
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if type(f[i]) == bool:
            if not dfs(i,1):
                return "No"
    return "Yes"

print(main())
### BUGGY CODE ###

# D
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))

# for i in range(N):
#     p[i] = (1+p[i])/2

ans = 0
# ans_index = 0
for i in range(0, N-K+1):
    ans_tmp = sum(p[i:i+K])
    ans = max(ans, ans_tmp)
#         ans_index = i

ans = (ans+K)/2

print(ans)

### FIXED CODE ###

# D

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

ans = sum(p[0:K])
ans_tmp = ans
for i in range(K, N):
#    print(p)
#    print(-p[i-K] + p[K])
    ans_tmp = ans_tmp - p[i-K] + p[i]
#    print(ans_tmp)
    ans = max(ans, ans_tmp)

ans = (ans+K)/2

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

#!/usr/bin/env python3

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10**12
    dp = [INF] * (N+1)
    dp[1] = 0
    for i in range(1,N):
        for j in range(1,K+1):
            if i+j > N:
                break
            else:
                dp[i+j] = min(dp[i+j],dp[i]+abs(h[i-1]-h[i+j-1]))
    print(dp[N])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10**12
    dp = [INF] * (N+1)
    dp[1] = 0
    for i in range(1,N):
        for j in range(1,K+1):
            if i+j > N:
                break
            else:
                dp[i+j] = min(dp[i+j],dp[i]+abs(h[i-1]-h[i+j-1]))
    print(dp[N])

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



from decimal import Decimal
from decimal import *
a, b, c = map(str, input().split())

getcontext().prec = 10000

a = Decimal(a)
b = Decimal(b)
c = Decimal(c)

if a**Decimal("0.5")  + b**Decimal("0.5") < c**Decimal("0.5"):
    print("Yes")
else:
    print("No")


### FIXED CODE ###



from decimal import Decimal
from decimal import *
a, b, c = map(str, input().split())

getcontext().prec = 500

a = Decimal(a)
b = Decimal(b)
c = Decimal(c)

if a**Decimal("0.5")  + b**Decimal("0.5") < c**Decimal("0.5"):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
a = 0
b = 0
L = [0] * Q
R = [0] * Q
ac_numbers = 0 
ac_count = 0 
for i in range(Q):
    a, b = map(int, input().split())
    L[i] = a
    R[i] = b
    for j in range(R[i]-L[i]+1): 
        if ac_count == 0:
            if S[L[i]-1+j] == 'A':
                ac_count = 1
        if ac_count == 1:
            if S[L[i]-1+j] == 'C':
                ac_count = 0
                ac_numbers += 1
            if S[L[i]-1+j] == 'A':
                ac_count = 1
            else:
                ac_count = 0
    print(ac_numbers)
    ac_count = 0
    ac_numbers = 0

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = [0]*Q 
R = [0]*Q
for q in range(Q):
    l, r = map(int, input().split())
    L[q] = l
    R[q] = r
ans = [0]*Q 
accumulative_count = [0]*(N) 
accumulative_count[0] = 0 
for i in range(1, N, 1): 
    accumulative_count[i] = accumulative_count[i-1]
    if (S[i-1:i] == 'A') & (S[i:i+1] == 'C'):
        accumulative_count[i] = accumulative_count[i-1] + 1
for q in range(Q):
    print(accumulative_count[R[q]-1] - accumulative_count[L[q]-1])
### BUGGY CODE ###

def main():
    N, D, A = map(int, input().split())
    B = []
    for i in range(N):
        X, H = map(int, input().split())
        B.append([X,H])

    B.sort()
    ans = 0
    ok = [False] * N
    for i in range(N):
        if ok[i]:
            continue
        cnt = B[i][1] // A if B[i][1] % A == 0 else B[i][1] // A + 1
        ans += cnt
        B[i][1] = 0
        ok[i] = True
        for j in range(min(i+1,N),N):
            if ok[j]:
                continue
            if B[j][0] <= B[i][0] + 2 * D:
                B[j][1] -= cnt * A
                if B[j][1] <= 0:
                    ok[j] = True
            else:
                break
    
    print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_right
import sys
input = sys.stdin.readline

def main():
    N, D, A = map(int, input().split())
    B = []

    for i in range(N):
        x, h = map(int, input().split())
        B.append((x,h))

    B.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = B[i]
    ans = 0
    ok = [False] * N
    S = [0] * (N + 1)
    for i in range(N):
        if S[i] < H[i]:
            cnt = (H[i] - S[i]) // A if (H[i] - S[i]) % A == 0 else (H[i] - S[i]) // A + 1
            ans += cnt
            search_max = bisect_right(X, X[i] + 2 * D)
            S[i] += cnt * A
            S[search_max] -= cnt * A
        
        S[i+1] += S[i]

    print(ans)



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

n, q = [int(e) for e in input().split()]
s = input()
ac = []
for i in range(n-1):
    if s[i:i+2] == 'AC':
        ac.append(i)
for i in range(q):
    l, r = [int(e) for e in input().split()]
    c = 0
    for j in range(l, r):
        if j-1 in ac:
            c += 1
    print(c)


### FIXED CODE ###

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


n = int(input())
data = [int(x) for x in input().split()]

data_elements = list(set(data))

for k in range(n):
    data_k = data[:]
    data_k.pop(k)
    data_k_elements = list(set(data_k))
    answer = 0
    for x in data_k_elements:
        i = data_k.count(x)

        answer += int(i*(i-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 ###

(N, K) = map(lambda a: int(a), input().split())
A = list(map(lambda a: int(a), input().split()))

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = i - A[i]
        t = i + A[i]
        for j in range(max(0, f), min(N, t+1)):
            B[j] += 1
    
    A = B

for _ in range(0, min(K,41)):
    proc()

print(" ".join(map(lambda a: str(a), A)))

### FIXED CODE ###

import numpy as np
from numba import njit

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

@njit
def solve(N,K,A):
    for j in range(0, K):
        B = np.zeros(N, dtype=np.int64)

        for i in range(0,N):
            f = max(0, i - A[i])
            t = min(N-1, i + A[i])
            #for j in range(max(0, f), min(N, t)+1):
            #    B[j] += 1
            B[f] += 1
            if t+1 < N:
                B[t+1] -= 1
        A = np.cumsum(B)
        if np.all(A == N):
            return A
        i += 1
    return A
    

print(" ".join(map(str, solve(N,K,A))))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 30
ans = 0
from bisect import bisect_left as bl, bisect_right as br
def sub(k):
    tmp = pow(2, k)
    tmp2 = tmp*2
    bb = [item%tmp2 for item in b]
    bb.sort()
    ans = 0
    for item in a:
        aa = item%tmp2
        if aa<=tmp:
            num = br(bb, tmp2-1-aa) - bl(bb, tmp-aa)
        else:
            num = br(bb, tmp2-1-aa) + (n - bl(bb, tmp*3-aa))
        ans += num
        ans %= 2
    return ans%2
    
for k in range(l):
    # i桁目を求める
    if sub(k):
        ans += pow(2, k)
print(ans)


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

a=(list(map(int,input().split())))
l=a[0]
r=a[1]
if(l-r>2021):
	print(0)
else:
	mini=2019
	i=l
	while(i<=r-1):
		j=i+1
		while(j<=r):
			p=(i*j)%2019
			mini=min(mini,p)	
			j+=1

		i+=1
	print(mini)

### FIXED CODE ###

a=(list(map(int,input().split())))
l=a[0]
r=a[1]
if(l-r>2021):
	print(0)
else:
	mini=2019
	i=l
	notFound=True
	while(i<=r-1 and notFound):
		j=i+1
		while(j<=r and notFound):
			p=(i*j)%2019
			
			mini=min(mini,p)
			if(mini==0):
				notFound=False	
			j+=1

		i+=1
	print(mini)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
t=[]
for i in range(m):
    for k in range(bc[i][0]):
        t.append(bc[i][1])
t.sort(reverse=True)
ans=0
 
for i in range(n):
    if i<len(t):
        ans+=max(a[i],t[i])
    else:
        ans+=a[i]
print(ans)


### FIXED CODE ###

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

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

import copy
n=int(input())
string=[]
ang=0
cou=0
for c in range(n):
    string.append(input())

charcou=[[0]*26 for i in [1]*n]
for c in range(n):
    for d in range(10):
        charcou[c][ord(string[c][d])-97]+=1

for c in range(n):
    for d in range(c+1,n):
        if charcou[c]==charcou[d]:
            ang+=1
print(ang)

### FIXED CODE ###

n=int(input())
string=[]
ang=0
charcou=[[0]*26 for i in [1]*n]
for c in range(n):
    string.append(input())
    for d in range(10):
        charcou[c][ord(string[c][d])-97]+=1
charcou.sort()
c=0
while c<n-1:
    comb=1
    while charcou[c]==charcou[c+1]:
        comb+=1
        c+=1
        if c>=n-1:
            break
    if comb!=1:
        ang+=int(comb*(comb-1)/2)
    c+=1
print(ang)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
  s = input()
  s = list(s)
  s.sort()
  S.append(s)

count = 0
for si in S:
  for sj in S:
    if si == sj:
      count += 1
ans = int((count - N)/2)
print(ans)

### FIXED CODE ###

#n,*sl, = map(lambda x:''.join(sorted(x)),open(0).read().split())
n = int(input())
sl = []
for i in range(n):
  S = ''.join(sorted(input()))
  sl.append(S)
count = 0
dict ={}

for s in sl:
  if s in dict:
    count += dict[s]
    dict[s] += 1
  else:
    dict[s] = 1
print(count)
### BUGGY CODE ###

t = int(input())
list_v = [int(x) for x in input().split()]

res = 1
for v in list_v:
  res = res * v
 
if res > 1000000000000000000:
	print(-1)
else:
	print(res)

### FIXED CODE ###

t = int(input())
list_v = list(map(int,input().split()))
 
res = 1
if 0 in list_v:
  res = 0
else:
  for v in list_v:
    res *= v
    if res > 10**18:
      res = -1
      break
print(res)
### BUGGY CODE ###

N = int(input())
names = []
words = {}
for i in range(N):
    name = input()
    if name in names:
      words[name] += 1
    else:
      words[name] = 1
      names.append(name)
        
        
max_name_list = []
for nm in words.items():
    if nm[1] == max(words.values()):
        max_name_list.append(nm[0])
max_name_list = sorted(max_name_list)
for i in range(len(max_name_list)):
    print(max_name_list[i])


### FIXED CODE ###

N = int(input())
words = {}
for i in range(N):
  name = input()
  if name not in words:
    words[name] = 1
  elif name in words:
    words[name] += 1
    
res_name = []
Max = max(words.values())
for i in words.keys():
  if words[i] == Max:
    res_name.append(i)
res_name = sorted(res_name)
for i in res_name:
  print(i)
### BUGGY CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))
d = []
c = []
for i in range(n):
    if not a[i] in d:
        d.append(a[i])
        c.append(a.count(a[i]))
c.sort(reverse=True)
print(n-sum(c[0:k]))


### FIXED CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))
d = {}
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
c = sorted(d.items(),key = lambda x:x[1], reverse=True)
ans = 0
for i in range(min(k,len(c))):
    ans += c[i][1]

print(n-ans)
### BUGGY CODE ###

N,P = map(int,input().split())
s = list(input())
S = [0]*N

for i in range(N):
    S[i] = int(s[i])

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (10**(i-1))
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

else:
    if P == 2:
        for i in range(N):
            if S[i] %2 == 0:
                count += i+1
    if P == 5:
        for i in range(N):
            if S[i] %5 == 0:
                count += i+1

print(count)

### FIXED CODE ###

N,P = map(int,input().split())
s = list(input())
S = [0]*N

for i in range(N):
    S[i] = int(s[i])

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (pow(10,(i-1),P) )
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

else:
    if P == 2:
        for i in range(N):
            if S[i] %2 == 0:
                count += i+1
    if P == 5:
        for i in range(N):
            if S[i] %5 == 0:
                count += i+1

print(count)