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

# D - Knapsack 1 Educational DP Contest / DP
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N,W = nm()
Weight = []
Value = []

for i in range(N):
    w,v = nm()
    Weight.append(w)
    Value.append(v)

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= Weight[i]:
            dp[i+1][j] = max(dp[i][j-Weight[i]]+Value[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

### FIXED CODE ###

# D - Knapsack 1 Educational DP Contest / DP
import numpy as np

N,W = map(int,input().split())

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)
### BUGGY CODE ###

N = int(input())

my_list = []

for i in range(N):
    s_i = input()
    my_dict = {}
    for j in range(10):
        if s_i[j] in my_dict:
            my_dict[s_i[j]] += 1
        else:
            my_dict[s_i[j]] = 1
    my_dict = sorted(my_dict.items())
    my_list.append(my_dict)

sum = 0

for i in range(N):
    num = 0
    for j in range(i + 1, N):
        if my_list[i] == my_list[j]:
            num += 1
    sum += num

print(sum)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = str(sorted(input()))
    if s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1
print(ans)
### BUGGY CODE ###

n=int(input())
b=[]
k=0
for i in map(int, input().split()):
  if k%2==0:
    b.append(i)
    k+=1
  else:
    b.insert(0,i)
    k+=1
if n%2!=0:
  b=b[::-1]
print(*b,sep=" ")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
print(*A[::-2],end=" ")
print(*A[N%2::2])
### BUGGY CODE ###

n = int(input())
m = list(map(int, input().split()))
for i in range(1,n+1):
    print(m.count(i))


### FIXED CODE ###

n = int(input())
a = [0] * n
m = list(map(int, input().split()))
for i in m:
    a[i-1] += 1
for i in a:
    print(i)
### BUGGY CODE ###

_,*p=map(int,open(0).read().split())
q=[]
while(len(p)!=0):
  t=p[0]
  q=[m for m in q if m%t!=0]
  p=[m if m!=t else 0 for m in p[1:] if m%t!=0 or m==t ]
  if 0 in p:
    p=[i for i in p if i!=0]
  else:q+=[t]
print(len(q))

### FIXED CODE ###

M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in sorted(l):
  a[i]+=1
  if a[i]==1:
    for j in range(2*i,M,i): a[j]+=2
print(a.count(1))
### BUGGY CODE ###

N=int(input())
li = list(map(int, input().split()))
c=0
ali=[]
for i in range(0,N):
  for j in range(0,N):
    for k in range(0,N):
      if li[i]+li[j]>li[k] and li[j]+li[k]>li[i] and li[k]+li[i]>li[j]:
        if li[i]!=li[j] and li[j]!=li[k] and li[k]!=li[i]:
          if i!=j and j!=k and k!=i:
            ali.append(sorted([i,j,k]))
def get_duplicate_list(seq):
    seen = []
    return [x for x in seq if not seen.append(x) and seen.count(x) == 2]
print(len(get_duplicate_list(ali)))

### FIXED CODE ###

N=int(input())
li = list(map(int, input().split()))
c=0
ali=[]
for i in range(0,N):
  for j in range(0,N):
    for k in range(0,N):
      if li[i]+li[j]>li[k] and li[j]+li[k]>li[i] and li[k]+li[i]>li[j]:
        if li[i]!=li[j] and li[j]!=li[k] and li[k]!=li[i]:
          if i!=j and j!=k and k!=i and i<j and j<k:
            ali.append(sorted([i,j,k]))
print(len(ali))
### BUGGY CODE ###

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

ans = 0

for x in range(k+1):
  if x > s:
    break
  for y in range(k+1):
    if x + y > s:
      break
    for z in range(k+1):
      if x + y + z > s:
        break
      if x+y+z == s:
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z <= k:
      ans += 1

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

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

for i in range(m):
    b, c = map(int, input().split())
    cnt = 0
    while 1:
        if a[0] < c and cnt < b:
            heapq.heapreplace(a, c)
            cnt += 1
        else:
            break

print(sum(a))

### FIXED CODE ###

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

for i in range(m):
    if a[0] >= bc[i][1]:
        break
    else:
        cnt = 0
        while cnt < bc[i][0]:
            heapq.heapreplace(a, bc[i][1])
            cnt += 1

print(sum(a))
### BUGGY CODE ###

N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[min(a-1,b-1), max(b-1,a-1)] = c 
del a, b, c, K

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0

def dfs(v, r, passed):
    global graph, dist
    passed.add(v)
    for nv in graph[v]:
        dist[r][nv] = dist[nv][r] =  min(dist[r][nv], dist[r][v] + cost[min(v,nv),max(v,nv)])
        if not nv in passed:
            dfs(nv, r, passed)
    passed.remove(v)
    return 0

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

passed = set()
for r in R:
    dfs(r, r, passed)
ans = min([mindist(r, R) for r in R])
print(ans)

### FIXED CODE ###

N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c 
del a, b, c, K

for k in range(N):
    for i in range(N):
        for j in range(i,N):
            dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k]+dist[k][j])

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

ans = min([mindist(r, R) for r in R])
print(ans)
### BUGGY CODE ###

from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return [d if d >= 0 else 1<<100 for d in D]
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append(j)

for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    print(a if a < 1 << 50 else -1)
    

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))
### BUGGY CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
A = list(map(int, input().split()))

ans = 0
MOD = 10**9 + 7
LCM = lcm_list(A)

for a in A:
  ans += LCM//a
  
ans = ans%MOD
print(ans)

### FIXED CODE ###

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

ans = 0
MOD = 10**9 + 7

LCM = A[0]
for i in range(1, N):
    LCM *= A[i]//fractions.gcd(LCM, A[i])
    
for a in A:
  ans += LCM//a
  
print(ans%MOD)
### BUGGY CODE ###

n = int(input())
ws = []
for _ in range(n):
    ws.append(input())

nums = []
for w in ws:
    v = [0] * 52
    for c in w:
        if "Z" < c:
            v[ord(c) - ord("a")] += 1
        else:
            v[ord(c) - ord("A") + 26] += 1
    nums.append(v)

ans = 0
found = []
for i in range(n):
    if i in found:
        continue
    r = 0
    for j in range(n):
        if j <= i:
            continue
        if j in found:
            continue
        v = 1
        for k in range(52):
            if nums[i][k] != nums[j][k]:
                v = 0
                break
        if v != 0:
            r += v
            found.append(j)
    ans += (r + 1) * r // 2

print(ans)


### FIXED CODE ###

n = int(input())
ws = [list(input()) for _ in range(n)]

def sort_l(l):
    l.sort()
    return l
ws = list(map(sort_l, ws))
ws.sort()

i = 0
j = 0
r = 0
ans = 0
while(i<n-1):
    i += 1
    if ws[i] == ws[j]:
        r += 1
    else:
        ans += r * (r+1) // 2
        r = 0
        j = i
ans += r * (r+1) // 2

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

def main(N, K, A):
    for i in range(K-1, N): # 0 から数えるから K-1
        # 総積
        this = A[i-(K-1):i+1]   # 直近3学期． i+1はスライスのときその数字は入らないから．

        # print
        if i != K-1:
            if this[-1] > before[0]:
                print('Yes')
            else:
                print('No')
        before = this


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    main(N, K, A)

### FIXED CODE ###

def main(N, K, A):
    for i in range(K, N): # 0 から数えるから K-1
        this = A[i]
        before = A[i-K]

        if this > before:
            print('Yes')
        else:
            print('No')



if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    main(N, K, A)
### BUGGY CODE ###

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

j = 1
temp = p_list[0]
for i in range(1,N):
  if p_list[i] > temp:
    continue
  if p_list[i] <= min(p_list[0:i+1]):
    j = j + 1
  else:
    temp = p_list[i]

print(j)

### FIXED CODE ###

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

j = 1
temp = p_list[0]
for i in range(1,N):
  if temp >= p_list[i]:
    j += 1
    temp = min(temp,p_list[i])

print(j)
### BUGGY CODE ###

import math
from functools import reduce

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

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

### FIXED CODE ###

n = int(input())
import math
l = []
for i in range(1,n +1):
    for j in range(1,n+1):
        l.append(math.gcd(i,j))
ans = 0
for i in range(1, n+1):
    for j in l:
        ans += math.gcd(j,i)
print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
edge = [[] for k in range(n)]
for k in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

from collections import deque
def dijkstra(start, edge_list):
    """
    edge_list = [[1, 2], [0, 2], [1, 3, 0], [2]]
    start = 0
    [0, 1, 1, 2] == dijkstra(start, edge_list, n)
    """
    
    n = len(edge_list)
    dist = [int(2e9) for _ in range(n)]
    dist[start] = 0
    parents = [0 for _ in range(n)]
    stack = deque([start])
    while len(stack) != 0:
        start = stack.pop()
        next_list = edge_list[start]
        for nex in next_list:
            if dist[start] + 1 < dist[nex]:
                dist[nex] = dist[start] + 1 
                stack.append(nex)
                parents[nex] = start
                
    return dist, parents

dist, parents = dijkstra(0, edge)

if max(dist) == int(2e9):
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)

### FIXED CODE ###

n, m = list(map(int, input().split()))
edge = [[] for k in range(n)]
for k in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

start = 0

from collections import deque
que = deque([start])
done = {start}
depth = [1e9]  * n
depth[start] = 0
parents = [-1] * n
while True:
    if len(que) == 0:
        break
    now = que.popleft()
    dep = depth[now]
    
    for node in edge[now]:
        if node not in done:
#             if dep < depth[node]:
            depth[node] = dep + 1
            parents[node] = now
            que.append(node)
        done.add(node)
#     done.add(now)
#     print(now)
if max(depth) == 1e9:
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)
### BUGGY CODE ###

import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

a,b = map(int,input().split())

ans = 1

for i in range(a,b+1):
	#print(i)
	ans = i*ans

if ans > 0:
	print("Positive")
elif ans == 0:
	print("Zero")
else:
	print("Negative")


### FIXED CODE ###

import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

a,b = map(int,input().split())

ans = 1

if a > 0 and b > 0:
	print("Positive")
elif a <= 0 and b >=0:
	print("Zero")
else:
	if (a-b)%2 == 0:
		print("Negative")
	else:
		print("Positive")
### BUGGY CODE ###

# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)


# dfs path detect
import collections

def isConnected(u, v):
    path = collections.deque()
    path.append(u)

    notVisited = [True] * V
    notVisited[u] = False

    while path:
        e = path[-1]
        for n in adj[e]:
            if n == v:
                return True
            elif notVisited[n]:
                path.append(n)
                notVisited[n] = False
        if e == path[-1]:
            path.pop()

    return False

def isStronglyConnected(u, v):
    if isConnected(u, v) and isConnected(v, u):
        print(1)
    else:
        print(0)


# Output
Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    isStronglyConnected(u, v)

### FIXED CODE ###

# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)

# Tarjan's strongly connected components algorithm(repetition)
import collections

S = collections.deque()
path = collections.deque()
index = 0
indices = [None] * V
lowlink = [None] * V
onStack = [False] * V
scc_id = [None] * V
parent = [0] * V

for v in range(V):
    if not indices[v]:
        index += 1
        indices[v] = index
        lowlink[v] = index
        S.append(v)
        path.append(v)
        onStack[v] = True

        while path:
            s = path[-1]
            adj_v = adj[s]
            for t in adj_v:
                if not indices[t]:
                    parent[t] = s
                    path.append(t)
                    S.append(t)
                    index += 1
                    indices[t] = index
                    lowlink[t] = index
                    onStack[t] = True
                    adj_v.remove(t)
                    break
            if s == path[-1]:
                for t in adj_v:
                    if onStack[t]:
                        lowlink[s] = min(lowlink[s], lowlink[t])
                p = parent[s]
                lowlink[p] = min(lowlink[p], lowlink[s])
                if indices[s] == lowlink[s]:
                    while S:
                        w = S.pop()
                        onStack[w] =False
                        scc_id[w] = s
                        if w == s:
                            break
                path.pop()


# Output
Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    if scc_id[u] == scc_id[v]:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

import sys
#大きすぎるとダメ
h,w=map(int,input().split())
sys.setrecursionlimit(h*w+10)
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

a, b = map(int, input().split())

def tower(i):
    h = 0
    for i in range(1, i+1):
        h += i
    return h

notFound = True
i = 0
while(notFound):
    i += 1
    for j in range(1,1000):
        if (tower(j)-i==a )and(tower(j+1)-i==b):
#            print("Found")
            notFound = False
print(i)


### FIXED CODE ###

# -*- coding: utf-8 -*-

a, b = map(int, input().split())

def tower(i):
    h = 0
    for i in range(1, i+1):
        h += i
    return h

delta = b - a

print(tower(delta) - b)
### BUGGY CODE ###

def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")

  for i in range(N):
    tar_X = list(X)
    first_1_count = base_1_count
    if tar_X[i] == "1":
      first_1_count -= 1
      tar_X[i] = "0"
    else:
      first_1_count += 1
      tar_X[i] = "1"
    target_int = int(''.join(tar_X), 2)
    count = 0
    num_of_1 = first_1_count
    while target_int != 0:
      target_int = target_int % num_of_1
      num_of_1 = bin(target_int).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

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

INF = float('inf')
d, g = map(int, input().split())
data = []
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = data[i][2]
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c, score, subtotal = data[j]
    t = p + f(data, total - subtotal, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))


### FIXED CODE ###

INF = float('inf')
d, g = map(int, input().split())
data = []
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = data[i][2]
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c, score, subtotal = data[j]
    t = p + f(data, total - subtotal, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))
### BUGGY CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s*=10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()