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

import sys
sys.setrecursionlimit(1000000)
F = sys.stdin
S = F.readline().strip("\n")
T = F.readline().strip("\n")

def operate(i, j):
    group = {i, j}
    if group == {"A"}: return "B"
    elif group == {"B"}: return "A"
    elif group == {""}: return ""
    elif group == {"", "A"}: return "A"
    elif group == {"", "B"}: return "B"
    elif group == {"A", "B"}: return ""

def initialize(L):
    d, length = 2, len(L)
    while d < length:
        d *= 2
    BT = [""] * (2 * d - 1)
    for i in range(length):
        K = d + i -1
        BT[d + i - 1] = L[i]
        while K > 0:
            K = (K - 1)//2
            BT[K] = operate(BT[2 * K + 1], BT[2 * K + 2])
    return BT

def Search(i, j, l, r, level, BT):
    if r < i or j < l: return ""
    elif i <= l <= r <= j: return BT[level]
    else:
        sl = Search(i, j, l, (l+r)//2, 2*level+1, BT)
        sr = Search(i, j, (l+r)//2 + 1, r, 2*level+2, BT)
        ans = operate(sl, sr)
        return ans


ST, TT = initialize(S), initialize(T)
maxS, maxT = len(ST)//2, len(TT)//2
Ans = ""
Q = int(F.readline().strip("\n"))
for _ in range(Q):
    a, b, c, d = map(int, F.readline().strip("\n").split(" "))
    if Search(a-1, b-1, 0, maxS, 0, ST) == Search(c-1, d-1, 0, maxT, 0, TT): Ans += "YES\n"
    else: Ans += "NO\n"
print(Ans)

### FIXED CODE ###

import sys
F = sys.stdin
S = F.readline().replace("A", "1").replace("B", "2").strip("\n")
T = F.readline().replace("A", "1").replace("B", "2").strip("\n")

sSum = [0] * (len(S)+1)
tSum = [0] * (len(T)+1)
for i in range(len(S)):
    sSum[i+1] = sSum[i] + int(S[i])
for i in range(len(T)):
    tSum[i+1] = tSum[i] + int(T[i])

Ans = ""
Q = int(F.readline().strip("\n"))
for _ in range(Q):
    a, b, c, d = map(int, F.readline().strip("\n").split(" "))
    if (sSum[b] - sSum[a-1]) % 3 == (tSum[d] - tSum[c-1]) % 3: Ans += "YES\n"
    else: Ans += "NO\n"
print(Ans)
### BUGGY CODE ###

N = int(input())
Word_list = []
ans = 0

for i in range(N):
    Gift = input()
    Word_list.append(Gift)
    Word_list.sort()

Before_Word = ""

for i in range(N):
    if Word_list[i] != Before_Word:
        ans += 1
        Before_Word = Word_list[i]

print(ans)

# 
# for i in range(N):
#     Gift = input()
#     CHECK = "Nothing"
#     for i in Word_list:
#         if i == Gift:
#             CHECK = "Exist"
#             break
#     if CHECK == "Nothing":
#         Word_list.append(Gift)
#         ans += 1
# # print(Word_list)
# print(ans)


### FIXED CODE ###

N = int(input())
Word_list = []
ans = 0

for i in range(N):
    Gift = input()
    Word_list.append(Gift)
Word_list.sort()

Before_Word = ""

for i in range(N):
    if Word_list[i] != Before_Word:
        ans += 1
        Before_Word = Word_list[i]

print(ans)

#
# for i in range(N):
#     Gift = input()
#     CHECK = "Nothing"
#     for i in Word_list:
#         if i == Gift:
#             CHECK = "Exist"
#             break
#     if CHECK == "Nothing":
#         Word_list.append(Gift)
#         ans += 1
# # print(Word_list)
# print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
box=[0]*(n-k+1)
for i in range(0,n-k+1):
    aa=0
    for j in range(0,k):
        aa+=p[i+j]+1
    box[i]=aa
print(max(box)/2)

### FIXED CODE ###

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

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

ans=s

for i in range(n-k):

    s += (p[i+k]-p[i])/2

    if s>ans:
        ans=s
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
queue = []
for i in range(n):
    name, time = input().split()
    queue.append({"name": name, "time": int(time)})
t = 0
while len(queue) != 0:
    #print([queue[i]["time"] for i in range(len(queue))])
    if queue[0]["time"] <= q:
        t += queue[0]["time"]
        name = queue[0]["name"]
        queue = queue[1:]
        print("{} {}".format(name, t))
    else:
        queue = queue[1:] + \
            [{"name": queue[0]["name"], "time":queue[0]["time"] - q}]
        t += q



### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
queue = deque()
for i in range(n):
    name, time = input().split()
    queue.append({"name": name, "time": int(time)})
t = 0
while len(queue) != 0:
    #print([queue[i]["time"] for i in range(len(queue))])
    head = queue.popleft()
    if head["time"] <= q:
        t += head["time"]
        name = head["name"]
        print("{} {}".format(name, t))
    else:
        queue.append({"name": head["name"], "time": head["time"] - q})
        t += q
### BUGGY CODE ###

# -*- coding: utf-8 -*
import sys
if False:
#if True:
    fh=open('ALDS1_1_D1.txt','r')
else:
    fh=sys.stdin
input=fh.readline

def main():
    n = int(input())
    a=[]
    for _ in range(n):
        a.append(int(input()))
    #print('a=',a)
    pmax=a[1]-a[0]
    for k in range(0, n-1):
        p=max(a[k+1:])-a[k] 
        if p > pmax:
            pmax=p

    print(pmax)
    
if __name__ == "__main__":
    main()



### FIXED CODE ###

# -*- coding: utf-8 -*
import sys
if False:
#if True:
    fh=open('ALDS1_1_D1.txt','r')
else:
    fh=sys.stdin
input=fh.readline

def main():
    n = int(input())
    a=[]
    for _ in range(n):
        a.append(int(input()))

    pmax=a[1]-a[0]
    pmin=a[0]
    for j in range(1, n):
        pmax = max(a[j]-pmin,pmax)
        pmin = min(pmin,a[j])

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

H,W=map(int,input().split())
INF=10**4
a=[[INF for j in range(W)] for i in range(H)]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i][j]=0

for i in range(H):
  for j in range(0,W-1):
    if a[i][j+1]>a[i][j]+1:
      a[i][j+1]=a[i][j]+1
for i in range(H-1,-1,-1):
  for j in range(W-1,0,-1):
    if a[i][j-1]>a[i][j]+1:
      a[i][j-1]=a[i][j]+1

for j in range(W):
  for i in range(0,H-1):
    if a[i+1][j]>a[i][j]+1:
      a[i+1][j]=a[i][j]+1
for j in range(W-1,-1,-1):
  for i in range(H-1,0,-1):
    if a[i-1][j]>a[i][j]+1:
      a[i-1][j]=a[i][j]+1

ans=0
for i in range(H):
  ans=max(ans,max(a[i]))
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

num = int(input())
data = []
for _ in range(num):
    data.append(sorted(input()))
data = sorted(data)
count = 0
for i in range(num):
    for j in range(i+1,num):
        if data[i] == data[j]:
            count+=1
        else:
            break
print(count)

### FIXED CODE ###

"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

n = int(input())

data = {}
for _ in range(n):
    temp = "".join(sorted(input()))
    # print(temp)
    if temp in data.keys():
        data[temp] += 1
    else:
        data[temp] = 1
# print(data)

answer = 0
for num in data.values():
    answer += (num*(num-1))//2
print(answer)
### BUGGY CODE ###

import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)
    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ma = 10**18
ans = 1
for i in a:
    ans = ans * i
    if ans > ma:
      ans = -1
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    ma = 10**18
    ans = 1
    for i in a:
        ans = ans * i
        if ans > ma:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        while self.parent[i] != i:
            i = self.parent[i]
        return i
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        self.parent[j] = i
N, M = map(int, input().split())
ps = list(map(int, input().split()))
ps = [i-1 for i in ps]
swap =[list(map(int, input().split())) for i in range(M)]
u = UnionFind(N)
for x, y in swap:
    u.union(x-1, y-1)
ans = 0
for i, p in enumerate(ps):
    if u.find(i, p):
        ans += 1
print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        self.parent[j] = i
N, M = map(int, input().split())
ps = list(map(int, input().split()))
ps = [i-1 for i in ps]
swap =[list(map(int, input().split())) for i in range(M)]
u = UnionFind(N)
for x, y in swap:
    u.union(x-1, y-1)
ans = 0
for i, p in enumerate(ps):
    if u.find(i, p):
        ans += 1
print(ans)
### BUGGY CODE ###

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

for i in range(m):
    a[-1] //= 2
    a = sorted(a)
    
print(sum(a))

### FIXED CODE ###

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

import heapq
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)

for i in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a,-(-b//2))
    
print(sum(a)*(-1))
### BUGGY CODE ###

n, a, b = map(int, input().split())
ans = 0

for i in range(1,n+1):
    mod = 0
    while n != 0:
        mod = mod + (i % 10)
        i = i // 10
    if mod >= a and mod <= b:
        ans += mod

print(ans)


### FIXED CODE ###

n, a, b = map(int, input().split())
ans = 0

for i in range(1,n+1):
    mod = 0
    div = i
    while div > 0:
        mod += (div % 10)
        div //= 10
    if mod >= a and mod <= b:
        ans += i

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

class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n
        self.memo = [0]*n

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    # 木の根を求める
    def findsp(self,x):
        if self.par[x] == x:
            self.memo[x] = 1
            return x
        else:
            self.par[x] = self.find(self.par[x])
            self.memo[x] = 1
            return self.par[x]

    def allfind(self,n):
        for i in range(n):
            if self.memo[i] == 1:
                self.findsp(i)
    
    def root(self,x):
        return self.par[x]

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)
    UF_k.allfind(n)
    UF_l.allfind(n)
    l = []
    for i in range(n):
        l.append((UF_k.root(i),UF_l.root(i)))
    for i in range(n):
        print(l.count(l[i]),end=' ')
    



### FIXED CODE ###

import bisect
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n
        self.memo = {}

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)
    l = []
    dic = {}
    for i in range(n):
        tmp = (UF_k.find(i),UF_l.find(i))
        l.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for fac in l:
        print(dic[fac],end=' ')
### BUGGY CODE ###

import copy
N=int(input())

A=list(map(int,input().split()))
AP=copy.copy(A)
AM=copy.copy(A)
ansP=0
for i in range(N):
    if i%2==1:
        if sum(AP[:i+1])>=0:
            #print(i,AP)
            a=sum(AP[:i+1])
            ansP+=(a+1)
            AP[i]-=(abs(a)+1)
    else:
        if sum(AP[:i+1])<=0:
            #print(i,AP)
            a=sum(AP[:i+1])
            ansP+=(abs(a)+1)
            AP[i]+=(abs(a)+1)
#print(AP)
ansM=0
for i in range(N):
    if i%2==0:
        if sum(A[:i+1])>=0:
            a=sum(A[:i+1])
            ansM+=(abs(a)+1)
            A[i]-=(abs(a)+1)
    else:
        if sum(A[:i+1])<=0:
            a=sum(A[:i+1])
            ansM+=(abs(a)+1)
            A[i]+=(abs(a)+1)
#print(A)
print(min(ansP,ansM))

### FIXED CODE ###

N=int(input())

L=list(map(int,input().split()))

Pnum=0
Psum=0
if L[0]>=1:
    Pnum=L[0]
else:
    Psum=1-L[0]
    Pnum=1
for i in range(1,N):
    if i%2==1:
        if Pnum+L[i]<=-1:
            Pnum=Pnum+L[i]
        else:
            Psum+=(Pnum+L[i]+1)
            Pnum=-1
    else:
        if Pnum+L[i]>=1:
            Pnum=Pnum+L[i]
        else:
            Psum+=(1-Pnum-L[i])
            Pnum=1
            
Mnum=0
Msum=0
if L[0]<=-1:
    Mnum=L[0]
else:
    Msum=L[0]+1
    Mnum=-1
for i in range(1,N):
    if i%2==0:
        if Mnum+L[i]<=-1:
            Mnum=Mnum+L[i]
        else:
            Msum+=(Mnum+L[i]+1)
            Mnum=-1
    else:
        if Mnum+L[i]>=1:
            Mnum=Mnum+L[i]
        else:
            Msum+=(1-Mnum-L[i])
            Mnum=1

print(min(Psum,Msum))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    ai = int(input())
    a.append(ai)

cnt = 0
i = 0
while True:
    if a[i] >= 2:
        cnt += 1
        a[i] -= 2

    elif a[i] == 1:
        if i + 1 >= n:
            break

        if a[i + 1] > 0:
            cnt += 1
            a[i] -= 1
            a[i + 1] -= 1

        else:
            i += 1

    else:
        i += 1

print(cnt)

### FIXED CODE ###

#B
n = int(input())
a = []
for i in range(n):
    ai = int(input())
    a.append(ai)

cnt = 0
i = 0
while i < n:
    if a[i] >= 2:
        pairs = a[i] // 2
        cnt += pairs
        a[i] -= (pairs * 2)

    elif a[i] == 1:
        if i + 1 >= n:
            break

        if a[i + 1] > 0:
            cnt += 1
            a[i] -= 1
            a[i + 1] -= 1

        else:
            i += 1

    else:
        i += 1

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

import itertools

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

conf_max = 0
for p in itertools.permutations(A):
    conf = 0
    for i in range(1, N):
        conf += min(p[i-1], p[0])
    if conf_max < conf:
        conf_max = conf

print(conf_max)

### FIXED CODE ###

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

conf_max = 0
for i in range(1, N):
    conf_max += A[i//2]

print(conf_max)
### BUGGY CODE ###

import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

q=int(input())
def sosuu(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
ans=0
A=[list(map(int,input().split())) for _  in range(q) ]
for l , r in A:
    for i in range(l,r+1):
        if i%2!=0 and sosuu(i) and sosuu((i+1)/2):
            ans+=1
    print(ans)
    ans=0

### FIXED CODE ###

N = 100001
A,B = [True]*N,[0]*N
A[0],A[1] = False,False
for i in range(2,N):
    if A[i]:
        for j in range(i*2,N,i):
            A[j] = False
c=0
for i in range(3,N):
    if A[i] and A[(i+1)//2]:
        c += 1
    B[i] = c
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(B[r]-B[l-1])
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
Ans = "YES"

for i in range(N):
    for j in range(N):
        if H[i] ==H[j] and i!=j:
            Ans = "NO"
    
print(Ans)

### FIXED CODE ###

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

Hlen = len(H)


Hsyugou = set(H)
Hhennkann = list(Hsyugou)
Hhennkannlen = len(Hhennkann)




if Hlen ==Hhennkannlen:
    print("YES")

else:
    print("NO")
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        continue
    for j in range(i+1,n):
        if done[j] != 1:
            if li[j]==li[i]:
                done[i]=1
                done[j]=1
                dp[i]=0
                dp[j]=0
            elif li[j]%li[i]==0:
                done[j]=1
                dp[j]=0
 
print(sum(dp))

### FIXED CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

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

K = int(input())
result = 0
import fractions

for a in range(1, K+1):
    for b in range(1, K+1):
        d = fractions.gcd(a, b)
        for c in range(1, K+1):
            result += fractions.gcd(d, c)

print(result)

### FIXED CODE ###

K = int(input())
import math
result = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        d = math.gcd(a, b)
        for c in range(1, K + 1):
            result += math.gcd(d, c)

print(result)
### BUGGY CODE ###

N,K=map(int,input().split())
s=input()
g=[]
l=0
for i in range(1,N):
    if s[i]!=s[i-1]:
        g.append(i-l)
        l=i
g.append(N-l)

M=len(g)
ans=0

if s[0]=="0":
    if K>M//2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>=N:
                break
            elif j==0:
                ans=max(ans,sum(g[0:2*K]))
            elif j%2==1:
                ans=max(ans,sum(g[j:j+2*K+1]))
        print(ans)
    
else:
    if K>=M//2+M%2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>=N:
                break
            elif j%2==0:
                ans=max(ans,sum(g[j:j+2*K+1]))
        print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
s=input()
g=[]
l=0
for i in range(1,N):
    if s[i]!=s[i-1]:
        g.append(i-l)
        l=i
g.append(N-l)

M=len(g)
ans=0
S=[0]
for h in range(M):
    S.append(S[h]+g[h])

if s[0]=="0":
    if K>M//2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>M:
                break
            elif j==0:
                ans=max(ans,S[j+2*K]-S[j])
            elif j%2==1:
                ans=max(ans,S[j+2*K+1]-S[j])
        ans=max(ans,S[M]-S[M-2*K])
        print(ans)
    
else:
    if K>=M//2+M%2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>M:
                break
            elif j%2==0:
                ans=max(ans,S[j+2*K+1]-S[j])
        ans=max(ans,S[M]-S[M-2*K])
        print(ans)
### BUGGY CODE ###

def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0

  if p == 2 or p == 5:
      for i in range(n):
          if int(s[i]) % p == 0:
              ans += i + 1
      print(ans)
      exit()

  else:
    chk = [0]*p
    chk[0] = 1
    m = 0
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i)+m)%p
      chk[m] += 1
    chk= [i*(i-1)/2 for i in chk]
    print(int(sum(chk)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

import math
def nCr(n, r):
  if n < r:
    return 0
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += nCr(i,2)
  print(ans)