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

Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
prime = [True for _ in range(10**5 + 10)]
prime[0] = prime[1] = False
for i in range(2, 320):
    if prime[i]:
        for j in range(i * 2, 10 ** 5 + 10, i):
            prime[j] = False
for q in query:
    ans = 0
    l, r = q
    for i in range(l, r + 1, 2):
        if prime[i] and prime[(i + 1) // 2]:
            ans += 1
    print(ans)

### FIXED CODE ###

Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
prime = [True for _ in range(10**5 + 1)]
prime[0] = prime[1] = False
for i in range(2, 320):
    if prime[i]:
        for j in range(i * 2, 10 ** 5 + 1, i):
            prime[j] = False
counter = [0 for _ in range(10 ** 5 + 1)]
for i in range(1, 10 ** 5 + 1):
    if prime[i] and prime[(i + 1) // 2]:
        counter[i] = counter[i - 1] + 1
    else:
        counter[i] = counter[i - 1]
for q in query:
    l, r = q
    print(counter[r] - counter[l - 1])
### BUGGY CODE ###

n = int(input())
s = input()

R_inds = []
G_inds = []
B_inds = []

for i in range(n):
    if s[i] == 'R':
        R_inds.append(i)
    elif s[i] == 'G':
        G_inds.append(i)
    else:
        B_inds.append(i)
    
ans = 0
for r in R_inds:
    for g in G_inds:
        big = max(r,g)
        small = min(r,g)
        bigger = big + (big - small)
        smaller = small - (big - small)
        if (big - small) % 2 == 0:
            middle = (big + small) // 2
        else:
            middle = -1
        
        if not (bigger in B_inds or smaller in B_inds or middle in B_inds):
            ans += len(B_inds)
        elif (bigger in B_inds and smaller in B_inds and middle in B_inds):
            ans += max(0,len(B_inds) - 3)
        elif (bigger in B_inds and smaller in B_inds and not middle in B_inds) or (smaller in B_inds and middle in B_inds and not bigger in B_inds) or \
            (middle in B_inds and bigger in B_inds and not smaller in B_inds):
            ans += max(0, len(B_inds) - 2)
        else:
            ans += max(0, len(B_inds) - 1)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
R_ls = [0] * n
G_ls = [0] * n
B_ls = [0] * n
R_csum = [0] * n
G_csum = [0] * n
B_csum = [0] * n
for i in range(n):
    if s[i] == 'R':
        R_ls[i] = 1
        R_csum[i] = R_csum[i-1] + 1
        G_csum[i] = G_csum[i-1]
        B_csum[i] = B_csum[i-1]
    elif s[i] == 'G':
        G_ls[i] = 1
        G_csum[i] = G_csum[i-1] + 1
        R_csum[i] = R_csum[i-1]
        B_csum[i] = B_csum[i-1]
    else:
        B_ls[i] = 1
        B_csum[i] = B_csum[i-1] + 1
        R_csum[i] = R_csum[i-1]
        G_csum[i] = G_csum[i-1]
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if (s[i] == 'R' and s[j] == 'G') or (s[i] == 'G' and s[j] == 'R'):
            now = B_csum[-1] - B_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'B':
                now -= 1
        elif (s[i] == 'R' and s[j] == 'B') or (s[i] == 'B' and s[j] == 'R'):
            now = G_csum[-1] - G_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'G':
                now -= 1
        elif (s[i] == 'G' and s[j] == 'B') or (s[i] == 'B' and s[j] == 'G'):
            now = R_csum[-1] - R_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'R':
                now -= 1
        else:
            now = 0
        ans += now
print(ans)
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
x = int(input())
#n, k = list(map(int, input().split()))
# a, b, c = list(map(int, input().split()))
#a = 0
#b = 0
for b in range(0, x+1):
    for a in range(0, x+1):
        if pow(a, 5)-pow(b, 5) == x:
            print(a, end=" ")
            print(b)
            exit()
        elif pow(a, 5)-pow(b*-1, 5) == x:
            print(a, end=" ")
            print(b*-1)
            exit()
        elif pow(a, 5)-pow(b*-1, 5) > x or pow(a, 5)-pow(b*-1, 5) < 0:
            break


### FIXED CODE ###

x = int(input())
#n, k = list(map(int, input().split()))
# a, b, c = list(map(int, input().split()))
#a = 0
#b = 0
for a in range(0, 1000):
    for b in range(0, 1000):
        if pow(a, 5)-pow(b, 5) == x:
            print(a, end=" ")
            print(b)
            exit()
        elif pow(a, 5)-pow(b*-1, 5) == x:
            print(a, end=" ")
            print(b*-1)
            exit()
        elif pow(-1*a, 5)-pow(b, 5) == x:
            print(-1*a, end=" ")
            print(b*-1)
            exit()
        elif pow(-1*a, 5)-pow(b*-1, 5) == x:
            print(-1*a, end=" ")
            print(b*-1)
            exit()
### BUGGY CODE ###

N = int(input())

ans=0
for i in range(1,N+1):
    for j in range(1,N-i+1):
        if (N-i)%j==0:
            ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
ans=0
for i in range(1,10**6+1):
    for j in range(1,1000001):
        if i*j>N-1:
            break
        else:
            ans+=1
print(ans)
### BUGGY CODE ###

N=int(input())

def div(n):
    res=0
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            res+=2
        if i**2==n:
            res-=1
    return res

ans=0
for i in range(1,N+1):
    ans+=i*div(i)
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,1+N):
    m=N-N%i
    n=N//i
    ans+=(i+m)*n//2
print(ans)
### BUGGY CODE ###

n,m,q=map(int,input().split())

A=[]
for i in range(m):
    b,c=map(int,input().split())
    A.append([b,c])
B=[]
for i in range(q):
    b,c=map(int,input().split())
    B.append([b,c,i])

C=[[0 for i in range(n+3)] for j in range(n+3)]
#print(C)
for i in range(m):
    C[A[i][0]][A[i][1]]+=1


A.sort(key=lambda x:x[1])
A.sort(key=lambda x:x[0])

B.sort(key=lambda x:x[1])
B.sort(key=lambda x:x[0])

D=[]

E=[[[0 for i in range(n+3)] for j in range(n+3)] for k in range(n+3)]
for l in range(n+2):
    for mrp1 in range(l,n+2):
        for rp1 in range(mrp1,n+2):

            for j in range(mrp1,rp1):
                for k in range(l,rp1):
                    E[l][mrp1][rp1]+=C[k][j]

co=0
ml=0
mr=0
for i in range(q):
    l=B[i][0]
    r=B[i][1]
    nu=B[i][2]
    if ml<l :
        co=0
        for j in range(l,r+1):
            for k in range(j,r+1):
                co+=C[j][k]
        D.append([co,nu])
    else:
        #for j in range(mr+1,r+1):
        #    for k in range(l,r+1):
        #        co+=C[k][j]
        co+=E[l][mr+1][r+1]
        D.append([co,nu])
    ml=l
    mr=r

D.sort(key=lambda x:x[1])
for i in range(q):
    print(D[i][0])


### FIXED CODE ###

import numpy

n,m,q=map(int,input().split())
M=[]
Q=[]
for i in range(m):
    M.append(list(map(int,input().split())))
for i in range(q):
    Q.append(list(map(int,input().split())))

#print(M)
#print(Q)

A=[[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
    A[M[i][0]][M[i][1]]+=1

B=[[0 for i in range(n+1)] for j in range(n+1)] #Aの累積和のリスト

#B[0][0]=A[0][0]
#for i in range(1,n+1):
#    B[i][0]=A[i][0]+B[i-1][0]
#    B[0][i]=A[0][i]+B[0][i-1]

#for i in range(1,n+1):
#    for j in range(1,n+1):
#        B[i][j]=A[i][j]+B[i-1][j]+B[i][j-1]

#print(A)
#print(B)

B = numpy.cumsum(A,axis=0)
C = numpy.cumsum(B,axis=1)

#print(C)

for i in range(q):
    le=Q[i][0]
    ri=Q[i][1]
    print(C[ri][ri]-C[ri][le-1]-C[le-1][ri]+C[le-1][le-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        stack.append(i)
    while stack:     
        x = stack.pop()
        visited[x] = 1
        conlist[x] = cnt
        for y in graph[x]:
            if visited[y] != 1:
                stack.append(y)
        
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
append = stack.append
pop = stack.pop
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        append(i)
    while stack:
        x = pop()
        visited[x] = 1
        conlist[x] = cnt
        for y in graph[x]:
            if visited[y] != 1:
                append(y)
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

import bisect
import copy

ans = 0
n = int(input())
l = list(map(int, input().split()))
l.sort()
for i in range(n-2):
  for j in range(i+1, n-1):
    a = l[i]
    b = l[j]
    ln = copy.copy(l)
    del ln[:j+1]
    k = bisect.bisect_right(ln, b - a)
    m = bisect.bisect_left(ln, a + b)
    ans += (m - k)
print(ans)

### FIXED CODE ###

import bisect
import copy

ans = 0
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
for i in range(n-2):
  for j in range(i+1, n-1):
    a = l[i]
    b = l[j]
    m = bisect.bisect_left(l, a + b)
    ans += (m - j - 1)
print(ans)
### BUGGY CODE ###

import math

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

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
print(dp[n - 1])


### FIXED CODE ###

import math

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

dp = [math.inf] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i))
print(dp[n - 1])
### BUGGY CODE ###

K, S = map(int,input().split())
p = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                p += 1
            if x + y + z > S:
                break
print(p)

### FIXED CODE ###

K, S = map(int,input().split())
p = 0
for x in range(K+1):
    if S-x <= 2*K:
        for y in range(min(S-x+1,K+1)):
            if S-x-y <= K:
                p += 1
print(p)
### BUGGY CODE ###


def solve():
    for n in range(1,N+1):
        cnt = 0
        for x in range(1,int(n**0.5)):
            for y in range(1,x+1):
                for z in range(1,x+1):
                    if x**2+y**2+z**2+x*y+y*z+z*x==n:
                        if x==y==z:
                            cnt += 1
                        else:
                            cnt += 3
                            x += 1
        print(cnt)

if __name__=="__main__":
    N = int(input())
    solve()


### FIXED CODE ###

N = int(input())
ls = [0]*(N+2)
 
for i in range(1,151):
    for j in range(1,151):
        for k in range(1,151):
            t = i*i + j*j + k*k + i*j + j*k + k*i 
            if t <= N :
                ls[t] += 1
 
for p in range(1,N+1):
    print(ls[p])
### BUGGY CODE ###

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

MAX = 10**18
ans = 1
for a in A_list:
  ans *= a
if ans > MAX:
  print(-1)
  exit()
print(ans)

### FIXED CODE ###

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

MAX = 10**18
ans = 1
isZero = False
isOverFlow = False
for a in A_list:
  if a == 0:
    isZero = True
    break
  if not isOverFlow:
    ans *= a
  if ans > MAX:
    isOverFlow = True

if isZero:
  print(0)
elif isOverFlow:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

cnts = []
for q in range(Q):
	l, r = map(int, input().split())
	cnt = S[l-1:r].count('AC')
	cnts.append(cnt)

for c in cnts:
	print(c)
	

### FIXED CODE ###

# GET AX
N, Q = map(int, input().split())
S = str(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
#N, Q = 8, 3
#S = 'ACACTACG'
#lr = [[3,7],[2,3],[1,8]]

a = [0]*len(S)
ac_num = 0
for i in range(N-1):
	a[i] = ac_num
	if S[i] == 'A' and S[i+1] == 'C':
		ac_num += 1
a[-1] = ac_num

for q in range(Q):
	l, r = lr[q]
	nl = a[l-1]
	nr = a[r-1]
	print(nr - nl)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
num = 1
for i in a:
    num *= i
if 10**18 < num:
    print(-1)
else:
    print(num)

### FIXED CODE ###

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

import bisect
import copy

n = int(input())
list1 = list(map(int,input().split()))
list1.sort()

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	list1_c = copy.deepcopy(list1) #ここでjのためのdeepcopyを更新
	for j in range(len(list1)):
		p = list1_c.pop(0)

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		#c = bisect.bisect_left(list1_c,a)
		d = bisect.bisect_right(list1_c,b)

		if d>=1:
			cout += d

print(cout)

### FIXED CODE ###

import bisect
import copy

n = int(input())
list1 = list(map(int,input().split()))
list1.sort()

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	for j in range(n-i-1):
		p = list1[j]

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1[j+1:],b)
		
		cout += d

print(cout)
### BUGGY CODE ###

import numpy as np

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

H = [int(input()) for i in range(N)]

Ha = np.sort(H)
Hd = Ha[1:] - Ha[:-1]

ans = 10**9
for i in range(N-K+1):
    if sum(Hd[i:i+K-1]) < ans:
        ans = sum(Hd[i:i+K-1])
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(input()) for i in range(N)]

H.sort()
ans = 10**9
for i in range(N-K+1):
    if (H[i+K-1]-H[i] < ans):
        ans = H[i+K-1]-H[i]

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

N = int(input())
S = input()
cnt = 0
for i in range(1000):
    C = [i//100, i//10%10, i%10]
    f = 0
    for s in S:
        if int(s) == C[f]:
            f += 1
        if f == 3:
           break
    if f == 3:
        cnt += 1
print(cnt)

### FIXED CODE ###

# sumitb2019_d.py
'''
重複考えないとどうなるか
-> 単に nC3 個( N 個から 3 つ選び出す順列と同じ)
というところまで考えたが、結局わからず解説AC
重複を考えるとかなり厳しいので重複がないものに着目する。
（今回であれば 000~999 までのパスワード）
発想の転換が凄い。これ思いつくの天才だろ…。
'''
N = int(input())
S = input()
cnt = 0
for i in range(1000):
    C = [str(i//100), str(i//10%10), str(i%10)]
    f = 0
    for s in S:
        if s == C[f]:
            f += 1
        if f == 3:
           break
    if f == 3:
        cnt += 1
    if cnt ==1000:
        break
print(cnt)
### BUGGY CODE ###

n,a,b=map(int,input().split())
def fac(N):
  s=1
  while N>=1:
    s=s*N
    N=N-1
  return (s)
def com(m,n):
  k=int(fac(m)/(fac(m-n)*fac(n)))
  return (k)
k=2**n-com(n,a)-com(n,b)-1
print (k)


### FIXED CODE ###

n,a,b=map(int,input().split())
p=1000000007
def pmod(N,K,p):
  s=1
  for i in range(K):
    s=(s*(N-i))%p
  return (s)

def bin(N):
    lists=[]
    t=0
    while N>0:
        lists.append(N%2)
        N=N//2
        t=t+1
    lists.append(t)
    return (lists)

def digb(N):
    t=0
    while N>0:
        N=N//2
        t=t+1
    return (t)

def mod(a,N,p):
    listm=[]
    for i in range(digb(N)):#2**(2**i)%pの余を記録
        listm.append(a*bin(N)[i])
        a=(a**2)%p
    s=1
    for i in range(digb(N)):
        if listm[i]!=0:
            s=(s*listm[i])%p
    return(s)

print ((mod(2,n,p)-pmod(n,a,p)*mod(pmod(a,a,p),p-2,p)-pmod(n,b,p)*mod(pmod(b,b,p),p-2,p)-1)%p)
### BUGGY CODE ###

# 動的計画法

n=int(input())
s=input()
dp=[[[0 for k in range(1000)] for j in range(4)] for i in range(n+1)]

dp[0][0][0]=1

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k]==0:continue
            dp[i+1][j][k]=1
            if j<=2:
                dp[i+1][j+1][k*10+int(s[i])]=1
cnt=0
for i in range(1000):
    if dp[n][3][i]==1:cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=list(map(int,list(input())))
ans=0
for i in range(10):
    try:
        ss=s[s.index(i)+1:]
        for j in range(10):
            try:
                sss=ss[ss.index(j)+1:]
                for k in range(10):
                    if k in sss:ans+=1
            except:pass
    except:pass

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

n, q = map(int, input().split())
s = list(input())
l,r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())

#acの場所把握
ac = []
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ac.append(i + 1)

for i in range(q):
    cnt = 0
    for j in range(len(ac)):
        if ac[j] >= l[i] and ac[j] + 1 <= r[i]:
            cnt += 1
    print(cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
l,r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())

#acの場所把握
ac = [0] * (n + 1)
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ac[i + 1] = ac[i] + 1
    else:
        ac[i + 1] = ac[i]

for i in range(q):
    print(ac[r[i] - 1] - ac[l[i] - 1])
### BUGGY CODE ###

mod = 10 ** 9 + 7

K = map(int, list(input()))
D = int(input())

s = 0
dp = [0] * D
for k in K:
    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7

K = input()
D = int(input())

s = 0
dp = [0] * D
for k in K:
    k = int(k)

    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
#import collections
#import sys
 
#input=sys.stdin.readline
 
N=int(input())
l=[]
 
for i in range(N):
    l.append(list(input()))
    l[i].sort()
    #clist.append(collections.Counter(list(input().replace("\n",""))))#ここは普通に入れてfor文でcounterする
 
count=0
 
for i in range(N):
    for j in range(i+1,N):
        if l[i]==l[j]:
            count+=1
            
print(count)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections 
 
N=int(input())
l=[]
 
for i in range(N):
    l.append(list(input()))
    l[i].sort()
    l[i]="".join(l[i])
    
clist=list(collections.Counter(l).values())

count=0
for c in clist:
    count+=int(c*(c-1)//2)
    
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

mod=998244353

from collections import Counter
import copy

C=Counter()
C[(0,0)]=1

for a in A:
    C2=copy.deepcopy(C)
    for s,k in C:
        if s+a<=S:
            C2[(s+a,k+1)]+=C[(s,k)]
    C=C2
        
    
ANS=0
for s,k in C:
    if s==S:
        ANS=(ANS+pow(2,N-k,mod)*C[(s,k)])%mod
print(ANS)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod=998244353

DP=[0]*(S+1)
DP[0]=pow(2,N,mod)

INV=pow(2,mod-2,mod)

for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]=(DP[i]*INV+DP[i+a])%mod
        
print(DP[S])
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = []
    B = []
    INF = 10 ** 18
    dp = [INF] * (N + 20000)
    dp[0] = 0
    for _ in range(M):
        a, b = list(map(int, input().split()))
        for i in range(N + 10000):
            if dp[i] == INF:
                continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
        
    return min(dp[N:])

print(solve())

### FIXED CODE ###

import numpy as np

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

A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

print(solve())
### BUGGY CODE ###

N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        else:
            return 0
ans=solve(N,K)
print(ans)

### FIXED CODE ###

N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        else:
            return 0
ans=solve(N,K)
print(ans)
### BUGGY CODE ###

from copy import deepcopy
rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
for i,s in enumerate(S[::-1]):
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*(10**i)%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*(10**i)%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = deepcopy(dp)
print(dp[amari])

### FIXED CODE ###

rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
mul = 1
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*mul%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*mul%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    mul = mul*10%13
print(dp[amari])
### BUGGY CODE ###

n = int(input())
a = input().split()
a = [int(_) for _ in a]

for i in range(n):
  print(a.count(i+1))

### FIXED CODE ###

n = int(input())
a = input().split()
a = [int(_) for _ in a]
b = [0]*n
for i in range(n-1):
  b[a[i]-1] += 1
  
for _ in b:
  print(_)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [list(map(int, readline().split())) for _ in range(N)]

    H = [[True] * N for _ in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(i + 1, N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return
                if k not in (i, j) and G[i][j] == G[i][k] + G[k][j]:
                    H[i][j] = False

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if H[i][j]:
                ans += G[i][j]

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if all(A[i][j] < A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()