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

n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + pow(10, n-i-1) * int(s[i])) % p
#         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

### FIXED CODE ###


def hoge():

    n, p = [int(c) for c in input().split()]
    s = input()    

    if p in (2,5):
        a = tuple(int(c)%p for c in s)
        out = 0
        for i,x in enumerate(a):
            if x==0:
                out += (i + 1)
    else:
        a = [0]*n
        tmp = 0
        for i in reversed(range(n)):
            tmp = (tmp + pow(10, n-i-1, p) * int(s[i])) % p
    #         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
            a[i] = tmp
        d = {i: 0 for i in range(p)}
        d[0] = 1
        out = 0
        for x in a[::-1]:
            out += d[x]
            d[x] += 1
    print(out)
hoge()
### BUGGY CODE ###

"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    d = 2
    while d * d <= a:
        while a%d==0:
            a//=d
            tmp.append(d)
        d += 1
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    l += diff

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v)
    ans += tmp
    ans %= mod

print(ans)

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

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

from collections import deque

def argmax_poss(xs):
    max_value = max(xs)
    out = []
    for i in range(len(xs)):
        if xs[i] == max_value:
            out.append(i)
    return(out)

h,w,m = map(int,input().split())
Ms = []

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = deque([])

for i in range(m):
  h,w = map(int,input().split())
  record.append((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h_poss = argmax_poss(h_scores)
max_w_poss = argmax_poss(w_scores)

out_pos_count = 0 

while record != deque([]):
    item = record.popleft()
    if item[0] in max_h_poss:
        if item[1] in max_w_poss:
            out_pos_count += 1
        

if len(max_h_poss) * len(max_w_poss) > out_pos_count:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)



### FIXED CODE ###

from collections import deque

h,w,m = map(int,input().split())
Ms = []

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = set()

for i in range(m):
  h,w = map(int,input().split())
  record.add((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h = max(h_scores)
max_w = max(w_scores)
max_h_poss = [i for i,v in enumerate(h_scores) if v == max_h]
max_w_poss = [i for i,v in enumerate(w_scores) if v == max_w]

out_pos_count = 0 

c = False

for i in max_h_poss:
    for j in max_w_poss:
        if (i,j) not in record:
            c = True
            break        

if c:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)
### BUGGY CODE ###

K, S = map(int,input().split())
X = 0
Y = 0
Z = 0
count = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x + y + z == S:
        count = count + 1
print(count)

### FIXED CODE ###

K, S = map(int,input().split())
count = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z <= K and z >= 0:
      count = count + 1
print(count)
### BUGGY CODE ###

from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = 0
#con = cmb(n,k,mod)
#print(con)
for i in range(k+1):
    ans += cmb(n,i,mod)*cmb(n-1,i,mod)
    ans %= mod
    
print(ans)

### FIXED CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = 0
#con = cmb(n,k,mod)
#print(con)
for i in range(min(k+1,n+1)):
    ans += cmb(n,i,mod)*cmb(n-1,i,mod)
    ans %= mod
    
print(ans)
### BUGGY CODE ###

from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

score = 1
for i in range(0,K):
    score*=A[i]

for i in range(K,N):
    if A[i] > A[i-K]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(K,N):
    if A[i] > A[i-K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
a = S[-1]
dp = np.zeros((n, 26), int)
x_ = dp[0]
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]]
if a == "?":
    x_[0:10] += 1
else:
    x_[int(a)] += 1
x_[13:] = x_[:13]
for s, x, i in zip(S[-2::-1], dp[1:], range(1, n)):
    l_ = l[i % 6]
    if s == "?":
        x[:13] += sum(x_[v:v+13] for v in l_)
    else:
        v = l_[int(s)]
        x[:13] += x_[v:v+13]
    x %= mod
    x[13:] = x[:13]
    x_ = x
print(x_[5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

from collections import deque

H, W = map(int,input().split())
coords = []
blacks = deque([])
for i in range(H):
    rows = list(input())
    coords.append(rows)
    for j,row in enumerate(rows):
        if row == "#":
            blacks.append((i,j,0))

ans = 0
while len(blacks) > 0: 
    h,w,dist = blacks.popleft()
    ans = max(dist,ans)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni = h + di
        nj = w + dj
        if 0 <= ni < H and 0 <= nj < W:
            if coords[ni][nj] == ".":
                blacks.append((ni,nj,dist+1))
                coords[ni][nj] = "#"

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int,input().split())
coords = []
blacks = deque([])
for i in range(H):
    rows = list(input())
    coords.append(rows)
    for j,row in enumerate(rows):
        if row == "#":
            blacks.append((i,j,0))

ans = 0
while len(blacks) > 0: 
    h,w,dist = blacks.popleft()
    ans = max(dist,ans)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni = h + di
        nj = w + dj
        if 0 <= ni < H and 0 <= nj < W:
            if coords[ni][nj] == ".":
                blacks.append((ni,nj,dist+1))
                coords[ni][nj] = "#"

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

#from math import gcd
from fractions import gcd
from functools import reduce
import sys
#import time


def input():
    return sys.stdin.readline()[:-1]


def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	mod = 10**9 + 7
	N = int(input())
	A = list(map(int, input().split()))

	ans = reduce(lcm, A)
	"""
	a = 1
	for i in A:
		a = lcm(a, i)
	"""
	#print(a, ans)
	B = [ans//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)


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

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


#dp = [[0] * (X+1) for _ in range(N+1)]
dp = [None]
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    dp.append([0] * (X+1))
    for x in range(X+1):

        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i 

print(dp[N][X] % MOD)


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

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

import fractions


n, m = map(int, input().split())
s = input()
t = input()

# よい文字列が存在する場合、答えは最小公倍数となる
l = (n * m) // fractions.gcd(n, m)

# 連結するとSになるXの位置リストを生成
ss = [l // n * i for i in range(n)]
# 連結するとTになるXの位置リストを生成
tt = [l // m * i for i in range(m)]

# 条件を満たすか判定
# for s_num in ss:
#     if s_num in tt:
#         s_idx = ss.index(s_num)
#         t_idx = tt.index(s_num)
#         if s[s_idx] != t[t_idx]:
#             l = -1
#             break

# 共通部分を取得
same = set(ss) & set(tt)
for item in same:
    if s[ss.index(item)] != t[tt.index(item)]:
        l = -1
        break
print(l)


### FIXED CODE ###

import fractions


n, m = map(int, input().split())
s = input()
t = input()

# 先頭文字が一致しない場合はよい文字列は存在しないので終了
if s[0] != t[0]:
    print(-1)
    exit()

# よい文字列が存在する場合、答えは最小公倍数となる
l = (n * m) // fractions.gcd(n, m)

# 連結するとSになるXの位置リストを生成
ss = set(l // n * i for i in range(1, n))
# 連結するとTになるXの位置リストを生成
tt = set(l // m * i for i in range(1, m))

# 共通部分を取得
same = list(ss & tt)

# メモリ開放
del ss
del tt

a = [s[item // (l // n)] for item in same]
b = [t[item // (l // m)] for item in same]

print(l) if a == b else print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=sorted(map(int,input().split()))

MAX=max(abs(A[0]),abs(A[-1]))
OK=-MAX**2-1
NG=MAX**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0
                
        if SC>=K:
            NG=mid
            break
    else:
        OK=mid
        
print(OK)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=sorted(map(int,input().split()))

M=[]
Z=[]
P=[]

for a in A:
    if a<0:
        M.append(-a)
    elif a==0:
        Z.append(a)
    else:
        P.append(a)

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int,input().split()))
a,m = 0,0
for i in range(n-1):
  for j in range(i+1,n):
    if h[j-1] >= h[j]:
      a += 1
      if j == n-1:
        m = max(m,a)
        a = 0
    else:
      m = max(m,a)
      a = 0
      break
print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int,input().split()))

count,m = 0,0

for i in range(n-1):
  if h[i] >= h[i+1]:
    count += 1
  else:
    m = max(m,count)
    count = 0
m = max(m,count)
print(m)
### BUGGY CODE ###

# Not Divisible

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

A.sort()

for i in range(len(A) - 1):
    if A[i] == 0:
        continue
    a = A[i]
    for j in range(i + 1, len(A)):
        if a == A[j]:
            A[i] = 0
        if A[j] == 0:
            continue
        if A[j] % a == 0:
            A[j] = 0

print(sum(map(lambda a: 0 < a, A)))


### FIXED CODE ###

# Not Divisible

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

check = [0] * 1000001
A.sort()

ok = [-1]
p = 0
for a in A:
    if a == p:
        if ok[-1] == p:
            ok = ok[:-1]
        continue
    p = a
    if check[a] == 1:
        continue
    for i in range(a, 1000001, a):
        check[i] = 1
    ok.append(a)

print(len(ok) - 1)
### BUGGY CODE ###

n = int(input())
ans = 0
for x in range(1,n+1):
    y = int(n/x)
    ans += y*(y+1)*x//2

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for x in range(1,n+1,1):
    y = int(n/x)
    ans += y*(y+1)*x/2

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

s = list(input())
qn = int(input())
q = []
rev = False

for i in range(qn):
    qi = input().split()
    if qi[0] == "1":
        rev = not rev
    else:
        if rev:
            if qi[1] == "1":
                qi[1] = "2"
            else:
                qi[1] = "1"
        q.append((2, (int(qi[1]), qi[2])))
if rev:
    q.append((1, ()))
for i in range(len(q)):
    if q[i][0] == 1:
        s = s[::-1]
    if q[i][0] == 2:
        if q[i][1][0] == 1:
            s = [q[i][1][1]] + s
        else:
            s.append(q[i][1][1])
print("".join(s))

### FIXED CODE ###

from collections import deque
s = deque(input())
qn = int(input())
q = []
rev = False

for i in range(qn):
    qi = input().split()
    if qi[0] == "1":
        rev = not rev
    else:
        if rev:
            if qi[1] == "1":
                qi[1] = "2"
            else:
                qi[1] = "1"
        q.append((2, int(qi[1]), qi[2]))
for i in range(len(q)):
    if q[i][0] == 2:
        if q[i][1] == 1:
            s.appendleft(q[i][2])
        else:
            s.append(q[i][2])
if rev:
    s = list(s)[::-1]
print("".join(s))
### BUGGY CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort(reverse=True)
    return divisors

def main():
    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1
    ans = 0
    for i in range(n):
        d = make_divisors(A[i])
        for x in d:
            if x != A[i]:
                if x in D:
                    break
            else:
                if D[x] >= 2:
                    break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort(reverse=True)
    return divisors

def main():
    A.sort()
    S = set(A)
    m = max(A)
    X = [0]*(m+1)
    for i in range(1, m+1):
        j = i
        if j not in S:
            continue
        while j <= m:
            X[j] += 1
            j += i
    #print(X)

    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1

    ans = 0
    for a in A:
        if X[a] == 1 and D[a] == 1:
            ans += 1
    print(ans)

    #for i in range(m+1):
    #    if X[i] == 1:
            #print(i)

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

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

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+ctL[connection[next[i]][j]]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print(' '.join(x))

### FIXED CODE ###

import copy
n,q=map(int,input().split())
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

k = int(input())

n = 1

if k % 2  == 0:
    n = -1
else:
    r = 7 % k
    s = r

    while True:
        if r == 0:
            break
        else:
            r = (r * 10 + s) % k
            n += 1

print(n)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k = int(input())

n = 1

if k % 2  == 0:
    n = -1
else:
    r = 7 % k
    s = r

    while True:
        if r == 0:
            break
        elif n > 1000000:
            n = -1
            break
        else:
            r = (r * 10 + s) % k
            n += 1


print(n)
### BUGGY CODE ###

#16:25
n,t = map(int,input().split())
wv = []
for _ in range(n):
  wv.append(list(map(int,input().split())))
wv.sort(key=lambda x:x[0])
now = [0 for _ in range(t+1)]
for i in range(n):
  w,v = wv[i]
  last = now
  now = []
  for f in range(t):
    if f >= w:
      now.append(max(last[f-w]+v,last[f]))
    else:
      now.append(last[f])
  now.append(max(last[-2]+v,last[-1]))
print(now[-1])

### FIXED CODE ###

n,t = map(int,input().split())
now = [0 for _ in range(t+1)]
wv = []
for _ in range(n):
  wv.append(list(map(int,input().split())))
wv.sort(key=lambda x:x[0])
for i in range(n):
  w,v = wv[i]
  last = now
  now = []
  for f in range(t):
    if f - w >= 0:
      now.append(max(last[f],last[f-w]+v))
    else:
      now.append(last[f])
  now.append(max(last[-2]+v,last[-1]))
  #print(now)
print(now[-1])
### BUGGY CODE ###

imos = [[0 for j in range(501)]for i in range(501)]
query = []
N,M,Q = map(int,input().split())
for i in range(M):
    L,R = map(int,input().split())
    imos[L][R] += 1
for i in range(Q):
    p,qq = map(int,input().split())
    query.append([p,qq])
for i in range(501):
    for j in range(1,501):
        imos[i][j] += imos[i][j-1]
for q in query:
    ans = 0
    for i in range(q[0],N+1):
        ans += imos[i][q[1]]
    print(ans)


### FIXED CODE ###

imos = [[0 for j in range(501)]for i in range(501)]
query = []
N,M,Q = map(int,input().split())
for i in range(M):
    L,R = map(int,input().split())
    imos[L][R] += 1
for i in range(Q):
    p,qq = map(int,input().split())
    query.append([p,qq])
for i in range(501):
    for j in range(1,501):
        imos[i][j] += imos[i][j-1]
for i in range(501):
    for j in range(1,501):
        imos[i][j] += imos[i-1][j]
for q in query:
    print(imos[N][q[1]]-imos[q[0]-1][q[1]])
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
s = set(A)
x = [0] * N

for i in s:
    x[i-1] += A.count(i)


o = '\n'.join(map(str, x))
print(o)


### FIXED CODE ###

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

for i in A:
    x[i-1] += 1

for i in x:
    print(i)
### BUGGY CODE ###

import itertools

N = int(input())
table = [input() for _ in range(N)]

count = 0

for a, b in list(itertools.product(range(N), repeat = 2)):
    symmetric = True
    new_table = []
    for i in range(N):
        string = table[(i+a)%N][b:] + table[(i+a)%N][:b]
        new_table.append(string)
    
    for i in range(N-1):
        string1 = new_table[i][i+1:]
        string2 = ''.join([s[i] for s in new_table[i+1:]])
        if string1 != string2:
            symmetric = False
            break
    
    if symmetric:
        count += 1

print(count)

### FIXED CODE ###

import itertools

N = int(input())
table = [input() for _ in range(N)]

count = 0

for b in range(N):
    symmetric = True
    new_table = []
    for i in range(N):
        string = table[i][b:] + table[i][:b]
        new_table.append(string)
    
    for i in range(N-1):
        string1 = new_table[i][i+1:]
        string2 = ''.join([s[i] for s in new_table[i+1:]])
        if string1 != string2:
            symmetric = False
            break
    
    if symmetric:
        count += N

print(count)
### BUGGY CODE ###

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

num = []
for i in range(N-1):
    a = A[i+1:]
    num.append(max(a)-A[i])
print(num.count(max(num)))

### FIXED CODE ###

from bisect import bisect_left

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

aa = A[:]
aa.sort()

ans = 0
num = []

for i in range(N-1):
    ind = bisect_left(aa, A[i])
    del aa[ind]
    
    num.append(aa[-1]-A[i])

print(num.count(max(num)))