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

def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])<<(N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - (1<<(N-1-i))
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + (1<<(N-1-i))
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')


### FIXED CODE ###

def solve():
  N = int(input())
  X = input()
  x = sum(map(int,list(X)))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  cnt1 = 0
  if x>1:
    for i in range(N):
      cnt1 += int(X[-i-1])*pow(2,i,x-1)
      cnt1 %= x-1
  cnt2 = 0
  for i in range(N):
    cnt2 += int(X[-i-1])*pow(2,i,x+1)
    cnt2 %= x+1
  
  ans = [0]*N
  for i in range(N):
    if X[i]=='1':
      if x==1:
        ans[i] = 0
      else:
        num = (cnt1-pow(2,N-i-1,x-1))%(x-1)
        ans[i] = dp[num]+1
    else:
      num = (cnt2+pow(2,N-i-1,x+1))%(x+1)
      ans[i] = dp[num]+1
  return ans
print(*solve(),sep='\n')
### BUGGY CODE ###

def main():
    import sys


    def input(): return sys.stdin.readline().rstrip()

    h, w = map(int, input().split())
    g = [[] for _ in range(h)]
    for i in range(h):
        g[i] = input()
    
    L = [[0]*w for _ in range(h)]
    R = [[0]*w for _ in range(h)]
    U = [[0]*w for _ in range(h)]
    D = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if g[i][j] == '#':
                continue
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j]+1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1]+1
    
    for i in range(h-1, -1, -1):
        for j in range(w-1, -1, -1):
            if g[i][j] == '#':
                continue
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1]+1
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j]+1
    
    ans = 0
    for i in range(h):
        for j in range(w):
            tmp = L[i][j]+U[i][j]+D[i][j]+R[i][j]-3
            ans = max(tmp, ans)
    print(ans)
            
                


            

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import numpy as np

    def input(): return sys.stdin.readline().rstrip()

    h, w = map(int, input().split())
    g = np.zeros((h, w), dtype=int)
    for i in range(h):
        g[i] = [int(s == '.') for s in input()]
    
    L = g.copy()
    R = g.copy()
    U = g.copy()
    D = g.copy()
    
    for i in range(1,h):
        U[i] = (U[i-1]+1)*g[i]
        D[~i] = (D[~i+1]+1)*g[~i]
    for j in range(1, w):
        L[:, j] = (L[:, j-1]+1)*g[:,j]
        R[:, ~j] = (R[:, ~j+1]+1)*g[:, ~j]
     
    ans = np.max(L+R+U+D-3)
    print(ans)
            
                
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
x=input()


def onecount(mojix):
    ones=0
    for j in mojix:
        if j=="1":
            ones+=1
    return ones


def popcount(new2bit,ones,count):
    #print("popcount start",new2bit,ones,count)
    
    if ones==0:
        return count
    
    else:
        ten=int(new2bit,2)
        div=ten%ones
        
        count+=1
        
        new2bit=bin(div)
        ones=onecount(str(new2bit))
        
        return popcount(new2bit,ones,count)

ones=onecount(x)

for i in range(N):
    
    
    if x[i]=="1":
        x_ith="0"

    else:
        x_ith="1"
        
    if i==0:
        new2bit=x_ith+x[i+1:]
    elif i<N-1:
        new2bit=x[:i]+x_ith+x[i+1:]
    else:
        new2bit=x[:i]+x_ith

    ones=onecount(new2bit)    
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(new2bit,ones,0))
    print(popcount(new2bit,ones,0))
        
        
    
    

### FIXED CODE ###

N=int(input())
x=input()
def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

# if GroundOnes>1:
#     for j in range(N):
#       TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
#       TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
# else:
#     for j in range(N):
#       TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
  
    
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-pow(2,N-i-1,ones)
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+pow(2,N-i-1,ones)
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    #print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))
### BUGGY CODE ###

n = int(input())
s = ['']*n
for i in range(n):
  s[i] = (''.join(sorted(input())))
a = []

l = len(s)
while l > 0:
  i = s[0]
  s = [ss for ss in s if ss != i]
  t = l - len(s)
  if t != 1:
    a.append(t)
  l = l-t

ans = 0
for i in range(len(a)):
  ans += a[i]*(a[i]-1)//2
print(ans)

### FIXED CODE ###

n = int(input())
s = ['']*n
for i in range(n):
  s[i] = (''.join(sorted(input())))
s.sort()

i=0
c=1
ans = 0
while i < n-1:
  while i+c < n and s[i] == s[i+c]:
    c += 1
  else:
    ans += c*(c-1)//2
    i += c
    c = 1

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

import math
import sys
sys.setrecursionlimit(1000000000)
from functools import lru_cache

N = int(input())
K = int(input())

# f(N,K)が回答になるようにする。
@lru_cache(maxsize=10009900)
def f(n, k):
    # 終了条件
    if n < 10:
        if k==0:
            return 1
        elif k==1:
            return n
        return 0
    
    ret = 0
    z = int(math.log10(n))
    keta = 10**z
    base = n % keta

    # 0のとき
    ret += f(keta-1, k)
    # 1..9のとき
    for i in range(1,10):
        if keta * (i+1) <= n:
            ret += f(keta-1, k-1)
        elif keta * i <= n:
            ret += f(base, k-1)

    return ret

print(f(N,K))

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)


N = int(input())
K = int(input())

from functools import lru_cache

@lru_cache(maxsize=10000)
def f(n,k):
    # print('n:{},k:{}'.format(n,k))
    if k == 0:
        return 1
    if k== 1 and n < 10:
        return n

    keta = len(str(n))
    if keta < k:
        return 0

    h = n // (10 ** (keta-1))
    b = n % (10 ** (keta-1))

    ret = 0
    for i in range(h+1):
        if i==0:
            ret += f(10 ** (keta-1) - 1, k)
        elif 1 <= i < h:
            ret += f(10 ** (keta-1) - 1, k-1)
        else:
            ret += f(b,k-1)
        
    return ret

print(f(N,K))
### BUGGY CODE ###

import numpy as np
import copy

n,m = map(int,input().split())
card_flg = [True for i in range(n + 1)]
false_flg = [False for i in range(n + 1)]



for i in range(m):
    l,r = map(int,input().split())
    card_flg_tmp = copy.copy(false_flg)
    card_flg_tmp[l:r + 1] = [True for i in range(l,r + 1)]
    card_flg = np.logical_and(card_flg, card_flg_tmp)

print(list(card_flg).count(True))


### FIXED CODE ###

import numpy as np
import copy

n,m = map(int,input().split())
max_l = 0
min_r = n

for i in range(m):
    l,r = map(int,input().split())
    max_l = max(max_l, l)
    min_r = min(min_r, r)

if max_l <= min_r:
    print(min_r - max_l + 1)
else:
    print(0)
### BUGGY CODE ###

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

max = 0
for i in range(N):
    count = 0
    for j in range(i, N-1):
        if H[j] >= H[j+1]:
            count += 1
        else:
            break
    if count > max:
        max = count

print(max)

### FIXED CODE ###

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

max = 0
i = 0
while N > i:
    count = 0
    j = i
    while N-1 > j:
        if H[j] >= H[j+1]:
            count += 1
            j += 1
        else:
            break
    if count > max:
        max = count
    i = j+1

print(max)
### BUGGY CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[{0}for _ in range(w)]
dp[0]={a[0][0]-b[0][0],b[0][0]-a[0][0]}
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    t=set()
    add=t.add
    if i:
      for v in dp[j]:
        add(v+x-y)
        add(v-x+y)
    if j:
      for v in dp[j-1]:
        add(v+x-y)
        add(v-x+y)
    if i+j:dp[j]=t
print(min(map(abs,dp[w-1])))

### FIXED CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))
### BUGGY CODE ###

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

S = list(map(int,input().split()))
T = list(map(int,input().split()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    l = sm[i-1][:]
    for j in range(1,M+1) :
        new = l[j] + sm[i][j-1]
        if S[i-1] == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l[j-1] # dp = 0
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)
### BUGGY CODE ###

N,W = map(int, input().split())
V = [[int(x) for x in input().split()] for _ in range(N)]


def knapsack(N,W,V):
    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(W+1):
        for j in range(N):
            w = V[j][0]
            v = V[j][1]
            if w <= i:
                dp[j+1][i] = max(dp[j][i-w]+v,dp[j][i])
            else:
                dp[j+1][i] = dp[j][i]
    return dp[N][W]

print(knapsack(N,W,V))

### FIXED CODE ###

N, W = map(int, input().split())
 
import numpy as np
dp = np.zeros(W + 1, dtype='int64')
 
for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)
 
print(dp[-1])
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline

def main():

    n=int(input())
    a = [int(x) for x in input().split()]
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

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

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    path = path if path[0] < path[1] else (path[1], path[0])
    if path not in paths:
        paths.append(path)
all_paths = []
for path in paths:
    all_paths += path
all_paths = set(all_paths)
count = 0
for n in range(1, N+1):
    is_good = 1
    if n not in all_paths:
        count += is_good
        continue
    for path in paths:
        if n not in list(path):
            continue
        if (path[0] == n):
            if (H[n-1] <= H[path[1]-1]):
                is_good = 0
                break
        else:
            if (H[n-1] <= H[path[0]-1]):
                is_good = 0
                break    
    count += is_good
print(count)

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(t.keys())
  for j in keys:
    nw = j - d[i][0]
    if nw < 0:
      continue
    nv = t[j] + d[i][1]
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))

### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import sys
from collections import defaultdict
#import heapq as hq

n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
D = defaultdict(list)

for a, b in L:
    D[a].append(b)

money =0
tmp = []
for l in range(1, limit+1):
    tmp +=D[l]
    if tmp:
        money+=max(tmp)
        tmp.remove(max(tmp))

print(money)


### FIXED CODE ###

import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline
n, limit = map(int, input().split())
dic = defaultdict(list)

for _ in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

L = []
ans = 0
for i in range(limit+1):
    for val in dic[i]:
        heapq.heappush(L, -val)
    if len(L):
        ans -= heapq.heappop(L)
print(ans)
### BUGGY CODE ###

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

for i in range(n):
  print(a.index(i+1)+1 , end=" ")

### FIXED CODE ###

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

s = sorted(range(n), key=lambda x:l[x])

for i in range(n):
  s[i]+= 1
  
print(*s)
### BUGGY CODE ###

N = int(input())
S = input()
s = list(S)
ret = set()
from itertools import combinations
for i in combinations(s, 3):
    ret.add(i)
print(len(ret))


### FIXED CODE ###

import bisect
N = int(input())
S = input()

str_dict = {}
for s in S:
    str_dict[s] = []

for i, s in enumerate(S):
    bisect.insort_right(str_dict[s], i)
cnt = 0
for i in range(10):
    for j in range(10):
        for t in range(10):
            test_str = str(i) + str(j) + str(t)
            now_idx = -1
            flg = True
            for k in test_str:
                if not k in str_dict.keys():
                    flg = False
                    break
                try:
                    tmp = str_dict[k][bisect.bisect_left(str_dict[k], now_idx+1)]
                    if tmp != now_idx:
                        now_idx = tmp
                    else:
                        flg = False
                        break
                except:
                    flg = False
                    break
            if flg:
                cnt += 1

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

import sys
sys.setrecursionlimit(1000000000)

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

count = 0
ans = 0
def dfs(s):
    if s + 1 < len(h):
        if h[s] >= h[s+1]:
            global count 
            count = count + 1
            dfs(s+1)
    

for i in range(len(h)):
    count = 0
    if not len(h) - i < ans:
        dfs(i)
    if count > ans :
        ans = count
        
print(ans)
    

### FIXED CODE ###

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

count = 0
ans = 0

for i in range(len(h)):
    if i + 1 < len(h):
        if h[i] >= h[i+1]:
            count = count + 1
        else:
            count = 0
    if count > ans :
        ans = count
        
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split(" ")]

flag = True

for i in A:
    if A.count(i) != 1:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split(" ")]

flag = True

A.sort()
for i in range(1,len(A)):
    if A[i-1] == A[i]:
        flag =False
        break

if flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import copy
n = int(input())
nums = list(map(int,input().split()))
for i in range(n):
    tmp = copy.deepcopy(nums)
    tmp.pop(i)
    tmp.sort()
    print(tmp[(n-1)//2])

### FIXED CODE ###

import copy
n = int(input())
nums = list(map(int,input().split()))
tmp = copy.deepcopy(nums)
tmp.sort()
cand1 = tmp[n//2]
cand2 = tmp[(n//2)-1]
for i in range(n):
    if nums[i] < cand1:
        print(cand1)
    else:
        print(cand2)
### BUGGY CODE ###

n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
p=[]
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = [False]*n
Q = deque()
Q.append([0,0])

while Q:
    node= Q.popleft()
    finish[node[0]]=True

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not finish[nxt]:
            Q.append([nxt,val])

print(*ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = {0}
Q = deque()
Q.append([0,0])
while Q:
    node= Q.popleft()
    finish.add(node[0])

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if nxt in finish:
            pass
        else:
            Q.append([nxt,val])

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

#(方針)「whiteから最も近いblackまでの距離」の最大値を求める
import queue
import copy

H,W = map(int,input().split())
white_index = []
Map = []
Map.append(['@']*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '.'): white_index.append([i+1,j])
Map.append(['@']*(W+2))


#幅優先探索
def bfs(sy,sx,Map):
  Map_[sy][sx] = 0
  qy,qx = queue.Queue(),queue.Queue()
  qy.put(sy),qx.put(sx)
  
  count = 0
  while(1):
   if(qx.empty() == True): return ans
    
   #座標の取り出し
   y,x = qy.get(),qx.get()
   if(Map_[y][x] == '#'): #ゴールなら終了
    return count

   #if((sy == 4)and(sx == 6)):
    #for i in range(H+2): print(Map_[i])
    #print('_____________')
    
   #次に進むところ
   vec_y = [0,0,1,-1]
   vec_x = [1,-1,0,0]
   for i in range(4):
     if(Map_[y+vec_y[i]][x+vec_x[i]] == '.'):
      Map_[y+vec_y[i]][x+vec_x[i]] = Map_[y][x] + 1
      qy.put(y+vec_y[i]),qx.put(x+vec_x[i])
     elif(Map_[y+vec_y[i]][x+vec_x[i]] == '#'): #ゴールなら終了
      count = Map_[y][x] + 1
      return count      
     

ans = 0
for i in range(len(white_index)):
 sy,sx = white_index[i][0],white_index[i][1]
 Map_ = copy.deepcopy(Map) #二次元リストのコピー
 ans = max(ans,bfs(sy,sx,Map_))  
print(ans)

### FIXED CODE ###

from collections import deque

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

by,bx= deque(),deque()
Map = []
Map.append('@'*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '#'):
      Map[i+1][j] = 0
      by.append(i+1),bx.append(j)
Map.append('@'*(W+2))      

cnt = 0
while(1):
  if(len(by) == 0):
    break
   
  ny,nx = by.popleft(),bx.popleft()
  vec_y,vec_x = [1,-1,0,0],[0,0,1,-1]
  for i in range(4):
      if(Map[ny+vec_y[i]][nx+vec_x[i]] == '.'):
         Map[ny+vec_y[i]][nx+vec_x[i]] = Map[ny][nx] + 1
         cnt = max(cnt, Map[ny][nx] + 1) 
         by.append(ny+vec_y[i]),bx.append(nx+vec_x[i])
  
print(cnt)
### BUGGY CODE ###

import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    for i in range(n-1,-1,-1):
        x=int(s[i:])
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)

### FIXED CODE ###

import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    reslst[0]+=1
    tmp=1
    now=0
    for i in [int(x) for x in s[::-1]]:
        now+=i*tmp
        now%=p
        reslst[now]+=1
        tmp=(tmp*10)%p
    
    for i in range(p):
        cnt+=reslst[i]*(reslst[i]-1)//2

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

N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9+7
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

t = 1
for a in A:
    t = a*t//gcd(a, t)

ans = 0
for a in A:
    ans += t//a%mod
    ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9+7
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

t = 1
for a in A:
    t = a*t//gcd(a, t)

ans = 0
for a in A:
    ans += t//a

print(ans%mod)
### BUGGY CODE ###

# D
import itertools
N = map(int, input().split())
L = list(map(int, input().split()))

value = 0
for i in itertools.combinations(L, 3):
    a, b, c = i
    
    if a<b+c:
        if b<c+a:
            if c<a+b:
                value+=1
print(value)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)