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

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

D, G = na()
p = []
c = []
for i in range(D):
    x, y = na()
    p.append(x)
    c.append(y)

ans = 99999999
for i in range(1<<D):
    ct = 0
    score = 0
    for j in range(D):
        if i>>j&1:
            score += c[j]
            score += p[j] * (j+1) * 100
            ct += p[j]
    while score < G:
        for j in range(D-1, -1, -1):
            if i>>j&1: continue
            for k in range(p[j]):
                if score < G:
                    score += (j+1)*100
                    ct += 1
    ans = min(ans, ct)
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

D, G = na()
p = []
c = []
for i in range(D):
    x, y = na()
    p.append(x)
    c.append(y)

ans = 99999999
for i in range(1<<D):
    ct = 0
    score = 0
    for j in range(D):
        if i>>j&1:
            score += c[j]
            score += p[j] * (j+1) * 100
            ct += p[j]
    for j in range(D-1, -1, -1):
        if i>>j&1: continue
        if score >= G: break
        g = (j+1)*100
        got = (G-score+g-1)//g
        score += min(got, p[j]) * g
        ct += min(got, p[j])
    ans = min(ans, ct)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def factorize(n, d):
  # if n == 0 or n == 1:
    # return []
    arr = []
    tmp = n
    while True:
      i = d[tmp]
      if i == 1:
        break
      #cnt=0
      while tmp%i==0:
        #cnt+=1
        tmp //= i
      arr.append(i)
    if tmp!=1:
      arr.append(tmp)
    if arr==[]:
      arr.append(n)
    return arr

def minimum_prime(n):
  # 試し割りをする際の最小の素数
  # エラトステネスの篩と同様の実装
    d = list(range(n+1))
    d[0] = 1
    for i in range(2, int(n**0.5) + 1):
        if d[i] != i:
          continue
        for j in range(i * 2, n + 1, i):
          if d[j] == j:
            d[j] = i
    return d  

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  max_arr = max(arr)
  d = minimum_prime(max_arr)
  
  if gcd(*arr) != 1:
    print('not coprime')
    exit()
  
  searched = []
  for a in arr:
    if a != 1:
      primes = factorize(a, d)
      for p in primes:
        if p in searched:
          print('setwise coprime')
          exit()
        searched.append(p)

  print('pairwise coprime')
    
  
main()

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def factorize(n, d):
  # if n == 0 or n == 1:
    # return []
    arr = []
    tmp = n
    while True:
      i = d[tmp]
      if i == 1:
        break
      #cnt=0
      while tmp%i==0:
        #cnt+=1
        tmp //= i
      arr.append(i)
    if tmp!=1:
      arr.append(tmp)
    if arr==[]:
      arr.append(n)
    return arr

def minimum_prime(n):
  # 試し割りをする際の最小の素数
  # エラトステネスの篩と同様の実装
    d = list(range(n+1))
    d[0] = 1
    for i in range(2, int(n**0.5) + 1):
        if d[i] != i:
          continue
        for j in range(i * 2, n + 1, i):
          if d[j] == j:
            d[j] = i
    return d  

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  max_arr = max(arr)
  d = minimum_prime(max_arr)
  dp = [0]*(max_arr+1)
  
  if gcd(*arr) != 1:
    print('not coprime')
    exit()
  
  searched = []
  for a in arr:
    if a != 1:
      primes = factorize(a, d)
      for p in primes:
        dp[p] += 1

  if max(dp) < 2:
    print('pairwise coprime')
  else:
    print('setwise coprime')
    

main()
### BUGGY CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy


N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    B,C=map(int, input().split())
    for _ in range(B):
        update.append(C)

update = sorted(update,reverse=True)

max_sum = sum(A)

for i in range(N):
    if i >= len(update):
        break
    if(A[i] > update[i]):
        break
    A[i] = update[i]
    max_sum = max(max_sum, sum(A))

print(max_sum)

### FIXED CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
from time import time

N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    temp = list(map(int, input().split()))
    update.append(temp)

# C_i の値をkeyにしてソートする
update = sorted(update,key = lambda x:x[1], reverse=True)

idx = 0
for b, c in update:
    for i in range(b):
        if idx >= N:
            break
        if A[idx] < c:
            A[idx] = c
            idx += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

import numpy as np

N = int(input())  
a = np.array(input().split(), dtype=np.int64)
b = np.zeros(N)
M = np.arange(N) + 1
    
for i in np.arange(N)[::-1]:
    A = a[np.where(M % (i+1) == 0)]
    if a[i] == 0:
        if np.sum(A) % 2  == 0:
            b[i] = a[i]
        else:
            b[i] = (a[i] + 1) % 2
    else:
        if np.sum(A) % 2  == 1:
            b[i] = a[i]
        else:
            b[i] = (a[i] + 1) % 2    
        
ans = np.where(b == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))

### FIXED CODE ###

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[i::i+1]
    if np.sum(A) % 2  == 0:
        a[i] = 0
    else:
        a[i] = 1
        
ans = np.where(a == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))
### BUGGY CODE ###

N = int(input())
S = list(input())
S.reverse()
ans = 0
for i in range(N):
    for k in range(N-1,i,-1):
        if S[i] != S[k]:
            for j in range(i,k):
                if j-i != k-j and S[j] != S[k] and S[i] != S[j]:
                    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R*G*B
for i in range(N):
    for k in range(i+1,N):
        if (k+i)%2 == 1:
            continue
        else:
            j = (k+i)//2
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

from itertools import combinations
N= int(input())
s = [''.join(sorted(list(input()))) for i in range(N)]
tmp = list(combinations(s,2))
result = [i for i in tmp if i[0] == i[1]]
print(len(result))

### FIXED CODE ###

def nCr(n, r):
    r = min(r, n-r)
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i
    return numerator // denominator

N= int(input())
s = [''.join(sorted(list(input()))) for i in range(N)]

dic={}
for i in s:
	if i in dic:
		dic[i] +=1
	else:
		dic[i] = 1

result = 0
for j in dic.values():
	if j > 1:
		result += nCr(j,2)

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

s=input()
t=input()

if sum(moji in set(s) for moji in t)!=len(t):print(-1)
n_itr=0
while len(t)!=0:
    n_itr+=1
    for i,moji in enumerate(s):
        if len(t)!=0 and t[0] == moji:
            t=t[1:]
            j=i
    if len(t)==0:
        print((n_itr-1)*len(s)+j+1)   

### FIXED CODE ###

import bisect
s=input()
t=input()
jisho={}
alphabets = [chr(ord('a') + i) for i in range(26)]
for moji in alphabets:
    jisho[moji] = [i for i,x in enumerate(s) if x==moji]
lis = [jisho[moji] for moji in t]

if [] in lis:
    print(-1)
else:    
    old=-1
    count=0
    for cand in lis:
        z=bisect.bisect(cand,old)
        if z==len(cand):
            num=min(cand)
        else:
            num=cand[z]
#         tes = [temp for temp in cand if temp>old]
#         if len(tes)==0:
#             num = min(cand)
#         else:
#             num = min(tes)
        if num<=old: count+=1
        old=num
    print(count*len(s)+old+1)
### BUGGY CODE ###

N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i] = map(int,input().split())
  
cnt=0
for i in range(N-1,-1,-1):
  s=A[i]%B[i]
  if s!=0:
    b= B[i]-s
    for j in range(0,i+1):
      A[j] += b
    cnt += b
  #print(i,A,cnt)

print(cnt)

### FIXED CODE ###

N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i] = map(int,input().split())
  
cnt=0
for i in range(N-1,-1,-1):
  A[i] += cnt
  s=A[i]%B[i]
  if s!=0:
    cnt +=B[i]-s
  #print(i,A,cnt)

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

def D():
    nxy=list(map(int,input().split()))
    len_list=[]
    len_count=0
    
    for i in range(1,nxy[0]+1):
        for j in range(1,nxy[0]+1):
            if i<j: len_list.append(min(abs(j-i),abs(nxy[1]-i)+1+abs(j-nxy[2])))
                
    
    len_list.sort()
    for k in range(1,nxy[0]):
        print(len_list.count(k))
    
        
if __name__=='__main__':
    D()

### FIXED CODE ###

def D():
    nxy=list(map(int,input().split()))
    count_list=[0]*nxy[0]
    
    for i in range(1,nxy[0]):
        for j in range(i+1,nxy[0]+1):
            mins=min(abs(j-i),abs(nxy[1]-i)+1+abs(j-nxy[2]))
            count_list[mins]+=1
            
    for i in range(1,nxy[0]):
        print(count_list[i])
            
        
if __name__=='__main__':
    D()
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while d != deque():
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

import bisect

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

ans = 0

for i in range(n):
	d = []
	for j in range(i+1,n):
		index = bisect.bisect_left(l,l[i]+l[j])
		for k in range(i+1,j):
			if l[j] < l[k] + l[i]:
				if [k,j] not in d:
					d.append([k,j])
					ans += 1
		for k in range(j+1,index):
			if l[k] < l[j] + l[i]:
				if [j,k] not in d:
					d.append([j,k])
					ans += 1
print(ans)


### FIXED CODE ###

import bisect

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

l.sort()
#print(l)
ans = 0
for i in range(n-1):
	a = l[i]
	for j in range(i+2,n):
		b = l[j]
		c = bisect.bisect_left(l,b-a+1)
		if j - c > 0:
			if i >= c:
				ans += j-i-1
			else:
				ans += j-c
		#print(i,j,c,ans)

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

N, K = map(int,input().split())
MOD = 10**9 + 7

state= [] # 同じ状態とみなしてよいものの個数の配列
i = 1
while i <= N:
    if i*i <= N:
        state.append(1)
        i += 1
    else:
        j = N // i # iの後における最大の数
        state.append(N//j-i+1) 
        i = N//j + 1

L = len(state)
#print(state)

# dp[k][x] : 最後が状態xであるようなk個の整数を並べる場合の数
dp = [[0]*L for _ in range(K+1)]
dp[0][0] = 1

#dp[k+1][x] = sum_{y: xを後ろにおける状態} dp[k][y]
for k in range(K):
    cum_sum = [0] * (L+1)
    for y in range(L): 
        cum_sum[y+1] = (cum_sum[y] + dp[k][y]) % MOD

    for x in range(L):
        # xを後ろにおけるような最大の状態はL-x-1
        dp[k+1][x] += cum_sum[L-x]
        dp[k+1][x] *= state[x]
        dp[k+1][x] %= MOD

#print(dp)
print(sum(dp[K]) % MOD)

### FIXED CODE ###

N, K = map(int,input().split())
MOD = 10**9 + 7

state= [] # 同じ状態とみなしてよいものの個数の配列
i = 1
while i <= N:
    if i*i <= N:
        state.append(1)
        i += 1
    else:
        j = N // i # iの後における最大の数
        state.append(N//j-i+1) 
        i = N//j + 1

L = len(state)
#print(state)

# dp[k][x] : 最後が状態xであるようなk個の整数を並べる場合の数
dp = [[0]*L for _ in range(K+1)]
dp[0][0] = 1

#dp[k+1][x] = sum_{y: xを後ろにおける状態} dp[k][y]
for k in range(K):
    cum_sum = [0] * (L+1)
    for y in range(L): 
        cum_sum[y+1] = (cum_sum[y] + dp[k][y]) % MOD

    for x in range(L):
        # xを後ろにおけるような最大の状態はL-x-1
        dp[k+1][x] += cum_sum[L-x]
        dp[k+1][x] *= state[x]
        dp[k+1][x] %= MOD

#print(dp)
print(sum(dp[K]) % MOD)
### BUGGY CODE ###

import bisect
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
ans = 0
right = 0
# print(l_list)
for i in range(n-2):
    for j in range(i+1,n-1):
        right = bisect.bisect_left(l_list[j+1:],l_list[i]+l_list[j])
        # print(right)
        ans += right
        
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
ans = 0
right = 0
# print(l_list)
for i in range(n-2):
    for j in range(i+1,n-1):
        right = bisect.bisect_left(l_list[j+1:],l_list[i]+l_list[j])
        # print(right)
        ans += right
        
print(ans)
### BUGGY CODE ###

from collections import Counter

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

d = Counter(A)

for i in range(M):
    b, c = map(int, input().split())
    for cand in [k for k in sorted(d.keys()) if k < c]:
        if b == 0:
            continue
        if d[cand] < b:
            d[c] += d[cand]
            b -= d[cand]
            d[cand] = 0
        else:
            d[cand] -= b
            d[c] += b
            b = 0

ans = 0
for k, v in d.items():
    if v == 0:
        continue
    ans += k * v

print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    A = []
    for i in list(map(int, input().split())):
        A.append((i, 1))
    for i in range(M):
        b, c = map(int, input().split())
        A.append((c, b))

    A = sorted(A)
    # print(A)
    cnt = 1
    ans = 0
    while cnt <= N:
        b, c = A.pop()
        ans += b
        if c > 1:
            c -= 1
            A.append((b, c))
        cnt += 1
    print(ans)


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

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    worst_score = 10 ** 12

    n, k = ns()
    a = na()
    f = na()
    a.sort()
    f.sort(reverse=True)
    score = [ai * fi for ai, fi in zip(a, f)]

    l = -1
    r = worst_score + 1

    while r - l > 1:
        middle = (l + r) // 2
        tmp_k = k
        for i in range(n):
            tmp = math.ceil((score[i] - middle) / f[i])
            tmp_k -= max(0, tmp)

            if tmp_k < 0:
                break

        if tmp_k >= 0:
            r = middle
        else:
            l = middle
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    worst_score = 10 ** 12

    n, k = ns()
    a = na()
    f = na()
    a.sort()
    f.sort(reverse=True)
    score = [ai * fi for ai, fi in zip(a, f)]

    l = 0
    r = worst_score

    while True:
        middle = (l + r) // 2

        tmp_k = k
        for i in range(n):
            tmp = (score[i] - middle + f[i] - 1) // f[i]
            tmp_k -= max(0, tmp)

            if tmp_k < 0:
                break

        if r - l == 1:
            print(middle if tmp_k >= 0 else middle + 1)
            exit(0)

        if tmp_k < 0:
            l = middle
        else:
            r = middle





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

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

MAX = 10**18
result = 1
M = FLI()

for m in M:
    result *= m

if result > MAX:
    print(-1)
else:
    print(result)

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

MAX = 10**18
result = 1
A = FLI()
if 0 in A:
    print(0)
    exit()
    
for i in A:
    result *= int(i)
    if result > MAX:
        print(-1)
        exit()

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

from itertools import product
def cnt(b,e,n_str):
  res=0
  for i in range(int(n_str)+1):
    if int(str(i)[0])==b and i%10==e:
      res+=1
  return res
def sol():
  n_str=input()
  return sum(cnt(b,e,n_str)*cnt(e,b,n_str) 
             for b,e in product(range(1,10),repeat=2))

print(sol())  



### FIXED CODE ###

from itertools import product
from functools import reduce
import operator
def prod(iterable):
    return reduce(operator.mul, iterable, 1)
def cnt_samelen(b,e,n_str):
  n0=int(n_str[0])
  if b>n0 or len(n_str)==1:
    return 0
  if b<n0:
    return b*int(10**(len(n_str)-2))
  
  return (int(n_str[1:-1])+1 if len(n_str)>2 else 1)-(1 if e>int(n_str[-1]) else 0)
def cnt(b,e,n_str):
  res=0
  l=len(n_str)
  if b==e and int(n_str)>=b:
    res+=1
  for i in range(l-2):
    res+=10**(i)
  res+=cnt_samelen(b,e,n_str)
  return res
def sol():
  n_str=input()
  return sum(cnt(b,e,n_str)*cnt(e,b,n_str) 
             for b,e in product(range(1,10),repeat=2))

print(sol())
### BUGGY CODE ###

mod=998244353
n,m,k=map(int,input().split())
fcl=[1]*(n+1)
for i in range(1,n+1):
  fcl[i]=(fcl[i-1]*i)%mod
def comb(x,y,p):
  return ((fcl[x]*pow(fcl[y],p-2,p))%p*pow(fcl[x-y],p-2,p))%p
ans=0
for i in range(k+1):
  ans+=m*pow(m-1,n-1-i,mod)*comb(n-1,i,mod)
  ans%=mod
print(ans)

### FIXED CODE ###

mod=998244353
n,m,k=map(int,input().split())
fcl=[1]*(n+1)
for i in range(1,n+1):
  fcl[i]=(fcl[i-1]*i)%mod
def comb(x,y,p):
  return ((fcl[x]*pow(fcl[y],p-2,p))%p*pow(fcl[x-y],p-2,p))%p
ans=0
for i in range(k+1):
  ans+=m*pow(m-1,n-1-i,mod)*comb(n-1,i,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

n, m = (int(i) for i in input().split())
ok = [1] * n
for i in range(1,m+1):
  tmp_l, tmp_r = (int(j) for j in input().split())
  filter_array = [1 if tmp_l<=k<=tmp_r else 0 for k in range(1,n+1)]
  ok = [x*y for (x,y) in zip(ok, filter_array)]
print(sum(ok))

### FIXED CODE ###

n, m = (int(i) for i in input().split())
ok = [1] * n
l, r = (1,n)
for i in range(1,m+1):
  tmp_l, tmp_r = (int(j) for j in input().split())
  if l < tmp_l:
    l = tmp_l
  if r > tmp_r:
    r = tmp_r

print( r-l+1 if r-l+1>0 else 0 )
### BUGGY CODE ###

X = input()
stack = []
for l in X:
	if stack == []:
		stack.append(l)
	elif stack[-1] == "S" and l == "T":
		stack = stack[:-1]
	else:
		stack.append(l)
print(len(stack))

### FIXED CODE ###

X = input()
stack = []
for l in X:
	if stack == []:
		stack.append(l)
	elif stack[-1] == "S" and l == "T":
		stack.pop()
	else:
		stack.append(l)
print(len(stack))
### BUGGY CODE ###

A=a=int(input())
count=2
samenumcount=0
y=[]
while A!=1:
    if A%count==0:
        samenumcount+=1
        y.append(count**samenumcount)
        A=A/count
    else:
        count+=1
        samenumcount=0
y.sort()

count2=0
for i in y:
    if a==1:
      break
    if a%i==0:
        #print(a,i)
        a=a/i
        count2+=1

print(count2)

### FIXED CODE ###

import numpy as np
import sys
A=a=int(input())
count=2
samenumcount=0
y=[]
 
if A==1:
    print(0)
    sys.exit()
 
while A!=1 and count<np.sqrt(a):
    if A%count==0:
        samenumcount+=1
        y.append(count**samenumcount)
        A=A/count
    else:
        count+=1
        samenumcount=0
if A!=1:
    y.append(A)
y.sort()
count2=0
for i in y:
    if a==1:
      break
    if a%i==0:
        a=a/i
        count2+=1
 
if count2==0:
    count2+=1

print(count2)