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

N,p=map(int,input().split())
s=input()
res=0
for i in range(N):
    val = int(s[i])
    if val%p==0:
        res += 1
    for j in s[i+1:]:
        val = (10*val+int(j))%p
        if val==0:
            res += 1
print(res)

### FIXED CODE ###

from collections import defaultdict as dd
N,p=map(int,input().split())
s=input()
res=0
dic=dd(int)
c = [0]*(N+1)

if p==2 or p==5:
    for i in range(N):
        now = int(s[N-i-1])%p
        if now==0:
            res += N-i
    print(res)
    exit()

for i in range(N):
    now = int(s[N-i-1])%p
    c[i+1] = (c[i]+pow(10,i,p)*now)%p
for val in c:
    dic[str(val)] += 1
    if dic[str(val)] >= 2:
        res += dic[str(val)]-1
print(res)
### BUGGY CODE ###

k, s = map(int,input().split())
ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                ans += 1
print(ans)


### FIXED CODE ###

k, s = map(int,input().split())
ans = 0
for i in range(k + 1):
    for j in range(k + 1):
        z = s - (i + j)
        if z >= 0 and z <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque


input = sys.stdin.readline
def IS(cb): return cb(input().strip())
def IL(cb): return [cb(s) for s in input().strip().split()]
def IR(cb, rows): return [IS(cb) for _ in range(rows)]
def ILL(cb, rows): return [IL(cb) for _ in range(rows)]


def solve():
    N, M = IL(int)
    AB = ILL(int, M)
    graph = [[False] * N for _ in range(N)]
    for a, b in AB:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    que = deque()
    que.append(0)
    visited = [False] * N
    visited[0] = True
    route = [0] * N
    while len(que):
        current = que.popleft()
        for next in (i for i in range(N) if graph[current][i]):
            if not visited[next]:
                visited[next] = True
                que.append(next)
                route[next] = current + 1

    print('Yes')
    for i in route[1:]:
        print(i)


solve()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque


input = sys.stdin.readline
def IS(cb): return cb(input().strip())
def IL(cb): return [cb(s) for s in input().strip().split()]
def IR(cb, rows): return [IS(cb) for _ in range(rows)]
def ILL(cb, rows): return [IL(cb) for _ in range(rows)]


def solve():
    N, M = IL(int)
    AB = ILL(int, M)
    graph = [[] for _ in range(N)]
    for a, b in AB:
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    que = deque()
    que.append(0)
    visited = [False] * N
    visited[0] = True
    route = [0] * N
    while len(que):
        current = que.popleft()
        for next in graph[current]:
            if not visited[next]:
                visited[next] = True
                que.append(next)
                route[next] = current + 1

    print('Yes')
    for i in route[1:]:
        print(i)


solve()
### BUGGY CODE ###

from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[False] * w for _ in range(h)]
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] = True

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))


### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

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

n,m=map(int,input().split())
INF=float("inf")

#始点,頂点の数,辺(頂点ごとの隣接行列)
def dijkstra(start,v,e):
    pre=[i for i in range(v)]
    x=set([i for i in range(v)])
    dist=[INF for _ in range(v)]

    dist[start]=0

    s=start
    while(len(x)>0):
        x.remove(s)

        min_x=-1
        min_dx=float("inf")
        for xi in x:
            if(dist[xi]>dist[s]+e[s][xi]):
                dist[xi]=dist[s]+e[s][xi]
                pre[xi]=s

            if(min_dx>dist[xi]):
                min_dx=dist[xi]
                min_x=xi

        s=min_x

    return pre

edge=[[INF for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a-1][b-1]=1
    edge[b-1][a-1]=1

mark=dijkstra(0, n, edge)
#print(mark)
print('Yes')
for i in range(1,len(mark)):
    print(mark[i]+1)

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())

q=deque([])

edge=[set([]) for _ in range(n+1)]
mark=[-1 for _ in range(n+1)]
used=[False for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].add(b)
    edge[b].add(a)

q.append(1)
mark[1]=1
used[1]=True
while(len(q)>0):
    vi=q.popleft()
    ei=edge[vi]
    for eij in ei:
        if(used[eij]):
            continue
        else:
            mark[eij]=vi
            used[eij]=True
            q.append(eij)

print('Yes')
for i in range(2,len(mark)):
    print(mark[i])
### BUGGY CODE ###

from collections import deque
s=list(input())
n=len(s)
K=int(input())
d=deque()
l=["" for _ in range((n*(n+1))//2)]
li=[]
cnt=0
st=""
cnt=0
for i in range(n):
    d.append(s[i])
#print(s,len(s))
for i in range(n):
    buf=deque()
    #print(s[i])
    #piv=ord(s[i])-97
    for j in range(n-i):
        v=d.popleft()
        buf.append(v)
        st="".join(buf)
        l[cnt]=st
        cnt=cnt+1
    buf.popleft()
    d=buf
l=list(set(l))
l.sort()
#print(l)
print(l[K-1])

### FIXED CODE ###

from collections import deque
s=list(input())
K=int(input())
#max(K)=5でaaaaaはa,aa,aaa,aaaa,aaaaaの順
#よって5文字まで取れば良い
d=deque()
for i in range(len(s)):
    d.append(s[i])
comp=[]
#print(d)
for i in range(len(s)):
    buf=deque()
    for j in range(len(d)):
        v=d.popleft()
        buf.append(v)
        if j<5:
            comp.append("".join(buf))
    d=deque()
    for j in range(len(buf)):
        d.append(buf[j])
    d.popleft()
comp=list(set(comp))
comp.sort()
print(comp[K-1])
### BUGGY CODE ###

N , M = map(int,input().split())
L = sorted(list(map(int,input().split())))
table =  [0,2,5,5,4,5,6,3,7,6]
L_val =sorted( list(map(lambda x:(table[x],x),L)))
#print(L_val)
number = ["0" for i in range(10**4+10)]
for x in L_val:
    number[x[0]] = str(x[1])

#print(number)
for i in range(10**4):
    tmp = number[i]
    if tmp=="0":
        continue
    for x in L_val:
        if  int(number[i+x[0]]) < int(tmp + str(x[1])):
            number[i+x[0]] = tmp + str(x[1])

print(number[N])


### FIXED CODE ###

N , M = map(int,input().split())
L = sorted(list(map(int,input().split())))
table =  [0,2,5,5,4,5,6,3,7,6]
L_val =sorted( list(map(lambda x:(table[x],x),L)))
number = ["0" for i in range(10**4+10)]

def comp(x,y):
    if len(x) >len(y):
        return 0
    elif len(x) < len(y):
        return 1
    else:
        for i in range(len(x)):
            if x[i] == y[i]:
                i+=1
            elif int(x[i]) < int(y[i]):
                return 1
            elif int(x[i]) > int(y[i]):
                return 0
        return 0



for x in L_val:
    number[x[0]] = str(x[1])

for i in range(10**4):
    tmp = number[i]
    if tmp=="0":
        continue
    for x in L_val:
        if  comp(number[i+x[0]],tmp + str(x[1])):
            number[i+x[0]] = tmp + str(x[1])

print(number[N])
### BUGGY CODE ###

import sys
n, ma, mb = map(int, input().split())
tc = [[] for _ in range(100 * n + 1)]
tn = [[] for _ in range(100 * n + 1)]
high = 100 * n + 1
for i in range(n):
  a, b, c = map(int, input().split())
  if a % ma == 0 and b % mb == 0 and a // ma == b // mb:
    high = c + 1
  tn[c].append((a, b))
  for j in range(1, high):
    for aa, bb in tc[j]:
      tn[j].append((aa, bb))
      tn[c + j].append((a + aa, b + bb))
      if (a + aa) % ma == 0 and (b + bb) % mb == 0 and (a + aa) // ma == (b + bb) // mb:
        high = c + j + 1
  tc = tn
  tn = [[] for _ in range(100 * n + 1)]
for i in range(1, 100 * n + 1):
  for a, b in tc[i]:
    if a % ma == 0 and b % mb == 0 and a // ma == b // mb:
      print(i)
      sys.exit()
print(-1)


### FIXED CODE ###

import sys
inf = float('inf')
n, ma, mb = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, 0, -1):
    for bb in range(400, 0, -1):
      if t[aa][bb] == inf:
        continue
      if t[a + aa][b + bb] > c + t[aa][bb]:
        t[a + aa][b + bb] = c + t[aa][bb]
  if t[a][b] > c:
    t[a][b] = c
result = inf
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == inf:
  print(-1)
else:
  print(result)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        x = n - i * r - j * g
        if x >= 0 and x % b == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
c = sorted([r, g, b])[::-1]
ans = 0
for i in range(n // c[0] + 1):
    x = n - i * c[0]
    for j in range(x // c[1] + 1):
        y = x - j * c[1]
        if y < 0:
            break
        elif y % c[2] == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    c[a] += 1
    c[b] += 1
    e[a].append(b)
    e[b].append(a)

me = max(c)

print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

for a, b in ab:
    print(d[a][b])



### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

n = int(input())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

e = [[] for _ in range(n)]

p = [0] * n
c = [0] * n
d = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0

q = [0]
p[0] = -1

while q:
    x = q.pop()
    temp = c[x]
    color = 1
    me = max(me, len(e[x]))
    #print(x, temp)
    for y in e[x]:
        if color == temp:
            color += 1
        if d[y] == 0:
            q.append(y)
            c[y] = color
            p[y] = x
            color += 1
    d[x] = 1

#print(c)
#print(p)

print(me)

for a, b in ab:
    if p[a] == b:
        print(c[a])
    else:
        print(c[b])
### BUGGY CODE ###

import sys
q = int(sys.stdin.readline().strip())
for _ in range(q):
    x = sys.stdin.readline().strip()
    y = sys.stdin.readline().strip()
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
                
    print(dp[m])



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

ans = 0
tmp1 = N//R + 1

for i in range(tmp1):
    tmp2 = (N - R*i)//G + 1
    for j in range(tmp2):
        tmp3 = (N - R*i - G*j)//B + 1
        for k in range(tmp3):
            if R*i+G*j+B*k == N:
                ans += 1



print(ans)

### FIXED CODE ###

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

ans = 0
tmp1 = N//R + 1

for i in range(tmp1):
    tmp2 = (N - R*i)//G + 1
    for j in range(tmp2):
        if (N - R*i - G*j)%B == 0:
            ans += 1



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

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
a=True
for i in t:
    if i in d:
        j=d.index(i)
        d=d[:j]+d[j+1:]
    else:
        a=False
        break
print('YES' if a else 'NO')

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
dd=dict()
td=dict()
for i in d:
    if i in dd:
        dd[i]+=1
    else:
        dd[i]=1
for i in t:
    if i in td:
        td[i]+=1
    else:
        td[i]=1
for i,j in td.items():
    if i not in dd:
        print('NO')
        exit()
    elif dd[i]<j:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = ListPos[i]
	#print(j)
	while(True):
		countHigh1 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		if (j == n+1):
			break
		countHigh2 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		countLow1 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	while(True):
		if (k == 0):
			break
		countLow2 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

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

t = True
cnt = 0

while t == True and cnt < len(bc):
  cnt += 1
  num = bc[cnt-1][0]
  large = bc[cnt-1][1]
  if large > min(a):
    for i in a:
      if i < large and a.index(i)+1 <= num:
        a[a.index(i)] = large
      else:
        break
    a.sort()
  else:
     t = False

print(sum(a))

### FIXED CODE ###

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

flg = 0
cnt = 0

for i in range(n):
  if bc[flg][1] >a[i] and flg < m:
    a[i] = bc[flg][1]
    cnt +=1
    if cnt == bc[flg][0]:
      flg += 1
      cnt = 0
      if flg == m:
        break
  else:
      break

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

def num():
    return int(input())
def nums():
    return list(map(int,input().split()))

X,Y,Z,K = nums()
A = nums()
B = nums()
C = nums()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = [bi + ai for bi in B for ai in A]
AB.sort(reverse=1)
res = []
for ab_sum in AB[:K]:
    for ci in C[:K]:
        res.append(ab_sum + ci)
res.sort(reverse=True)
for ans in res[:K]:
    print(ans)

### FIXED CODE ###

def num():
    return int(input())
def nums():
    return list(map(int,input().split()))

X,Y,Z,K = nums()
A = nums()
B = nums()
C = nums()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = [bi + ai for bi in B for ai in A]
AB.sort(reverse=1)
res = []
for ab_sum in AB[:K]:
    for ci in C[:K]:
        res.append(ab_sum + ci)
res.sort(reverse=True)
for ans in res[:K]:
    print(ans)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    B = LI()
    mb = B[-1]
    for i in range(N):
        if A[i] == B[i]:
            if B[i] < mb:
                p = bisect.bisect_left(B[i+1:],B[i]+1) + i+1
                if p > N-1:
                    print('No')
                    return
            else:
                p = N-1 - i
            t = B[i]
            B[i] = B[p]
            B[p] = t
            if A[i] == B[i]:
                print('No')
                return
    print('Yes')
    print(*B,sep=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    B = LI()

    c = collections.Counter()
    for x in A:
        c[x] += 1
    for x in B:
        c[x] += 1
        if c[x] > N:
            print('No')
            return

    s = 0
    for i in range(N):
        if A[i] == B[i]:

            p = bisect.bisect_left(B,B[i]+1,i+1)
            if p > N-1:
                p = s
                s += 1
                while B[i] == B[s]:
                    s+=1

            B[i],B[p] = B[p],B[i]
    print('Yes')
    print(*B,sep=' ')

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

N,K = [int(i) for i in input().split()]
S = list(map (int, list(input())))
start = S[0]
row = []
state = [0,start]
for i in S:
    if i == start:
        state[0] += 1
    else:
        row.append(state)
        start = i
        state = [1,i]
row.append(state)
ans = []
for i in range(max(len(row)-K*2+1,1)):
    if row[i][1] == 1:
        ans.append(sum([row[i][0] for i in range(i,min(K*2+i+1,len(row)))]))
    else:
        ans.append(sum([row[i][0] for i in range(i,min(K*2+i,len(row)))]))
print(max(ans))

### FIXED CODE ###

N,K = map(int,input().split())
S = input()
row = []
count = 1
flag = S[0]
for i in range(1,N):
    if S[i] != flag:
        row.append([count,flag])
        count = 1
        flag = S[i]
    else:
        count += 1
row.append([count,flag])
inst = 0
ans,temp = 0,0
left,right = 0,0
for i in range(len(row)):
    if row[i][1] == "1":
        temp += row[i][0]
    else:
        inst += 1
        if inst <= K:
            temp += row[i][0]
        else:
            temp -= row[left][0]
            if row[left][1] == "1":
                temp -=row[left+1][0]
                left += 1
            temp += row[i][0]
            left += 1
    ans = max(ans,temp)
print(ans)
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
C1 = C_T[0]
for C2 in C_T[1:]:
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        cost = dp[j][0]
        for k in range(H+1):
            cost += (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = cost = min(dp[j][k+1], cost)
    ans += dp[H][H]
    C1 = C2
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
table = [int(s[i:]) % 2019 for i in range(n)]+[0]
count = [0 for _ in range(2019)]
ans = 0
for t in table:
    if count[t] != 0:
        ans += count[t]
    count[t] += 1
print(ans)


### FIXED CODE ###

s = input()
n = len(s)
table = [0 for _ in range(n + 1)]
for i in range(n):
    table[-2 - i] = (int(s[-1 - i]) * pow(10, i, 2019) + table[-1 - i]) % 2019
count = [0 for _ in range(2019)]
ans = 0
for t in table:
    if count[t] != 0:
        ans += count[t]
    count[t] += 1
print(ans)