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

def factors(n):
    return [i for i in range(2, n) if n % i == 0]


X = int(input())

prime_l = factors(X)
while True:
    for i in prime_l:
        if X % i == 0:
            break
    prime_l.append(X)
    X += 1
print(X)


### FIXED CODE ###

import random


def is_prime3(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    # n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1) >> 1
    while d & 1 == 0:
        d >>= 1

    # 判定をk回繰り返す
    for i in range(k):
        a = random.randint(1, q-1)
        t = d
        y = pow(a, t, q)
        # [0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q-1 and t & 1 == 0:
            return False
    return True


X = int(input())

while not is_prime3(X):
    X += 1

print(X)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    zeros=[0 for i in range(n)]

    if min(a)==n:
        print(*a)
        exit()

    for i in range(k):
        x=zeros.copy()
        for j in range(n):
            if a[j]==0:
                l=j
                r=min(j+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                #print(r)
                    x[r]+=-1
                #print(x)
            else:
                l=max(0,j-a[j])
                r=min(j+a[j]+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                    #print(r)
                    x[r]+=-1
                #print(x)
        ruiseki=[0]*n
        ruiseki[0]=x[0]
        a[0]=ruiseki[0]
        for i in range(1,n):
            ruiseki[i]=ruiseki[i-1]+x[i]
            a[i]=ruiseki[i]
 
        #print(*ruiseki)
    print(*a)
if __name__=="__main__":
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    zeros=[0]*n

    if min(a)==n:
        print(*a)
        exit()

    for i in range(k):
        x=zeros.copy()
        for j in range(n):
            if a[j]==0:
                l=j
                r=min(j+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                #print(r)
                    x[r]+=-1
                #print(x)
            else:
                l=max(0,j-a[j])
                r=min(j+a[j]+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                    #print(r)
                    x[r]+=-1
                #print(x)
        ruiseki=[0]*n
        ruiseki[0]=x[0]
        a[0]=ruiseki[0]
        for i in range(1,n):
            ruiseki[i]=ruiseki[i-1]+x[i]
            a[i]=ruiseki[i]
        if min(a)==n:
            print(*a)
            exit()
 
        #print(*ruiseki)
    print(*a)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import bisect

def main():
  n, k = map(int, input().split())
  minus = []
  zero = 0
  plus = []
  lm = 0
  lp = 0
  J = 0
  for i in map(int, input().split()):
    if i < 0:
      minus.append(-i)
      lm += 1
    elif i == 0:
      zero += 1
    else:
      plus.append(i)
      lp += 1

  minus.sort()
  plus.sort()

  J = lm*lp + zero*(n-zero) + zero*(zero-1)//2
  def test(x):
    count = 0
    if x < 0:
      x = -x
      for i in minus:
        count += lp - bisect.bisect_left(plus, -(-x//i))
      return count >= k

    if x == 0:
      return J >= k

    count = J
    for i in range(lm-1):
      t = minus[i]
      count += bisect.bisect_right(minus[i+1:], x//t)
    for i in range(lp-1):
      t = plus[i]
      count += bisect.bisect_right(plus[i+1:], x//t)
    return count >= k

  ng = -(10**18)
  ok = 10**18
  while ok-ng > 1:
    mid = (ok+ng)//2
    if test(mid):
      ok = mid
    else:
      ng = mid
  print(ok)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)
### BUGGY CODE ###

import sys

def main():
    
    a,b,k = map(int, input().split())
    if a + b <= k:
        print(0,0)
        sys.exit()
    else:    
        for i in range(k):
            if a > 0:
                a = a-1
            if a <= 0 and b > 0:
                b = b-1
                break
        print(a,b)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():
    
    input = sys.stdin.readline
    a,b,k = map(int, input().split())
    if a + b <= k:
        print(0,0)
        sys.exit()
    else:    
        if a < k:
            b = b-(k-a)
            a = 0
        else:
            a = a-k
        print(a,b)
            

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

N = int(input())
words = list()
count = 0
for _ in range(N):
    words.append(sorted(input()))

for i in range(N):
    for j in range(i+1, N):
        if words[i] == words[j]: count += 1

print(count)

### FIXED CODE ###

N = int(input())
words = []
dic = {}
count = 0

for _ in range(N):
    words.append(str(sorted(input())))

for word in words:
    if word in dic:
        count += dic[word]
        dic[word] += 1
    else:
        dic[word] = 1

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

N = int(input())
Array = []
for i in range(N):
    next_x, next_y = map(int, input().split())
    Array.append([next_x,next_y])

def Chevdistaaa (xdist,ydist):
    xdists = xdist - ydist
    ydists = xdist + ydist
    return(xdists,ydists)


Array2 = []
Point1x = 0
Point1y = 0
Point2x = 0
Point2y = 0
for i in range(N):
    for j in range(N):
        Point1x = Array[i][0]
        Point1y = Array[i][1]
        Point2x = Array[j][0]
        Point2y = Array[j][1]
        Dist = abs(Point1x -  Point2x) + abs(Point1y - Point2y)
        Array2.append(Dist)

print(max(Array2))

### FIXED CODE ###

N = int(input())
Array1 = []
Array2 = []

for i in range(N):
    next_x, next_y = map(int, input().split())
    s = next_x + next_y
    t = next_x - next_y
    Array1.append(s)
    Array2.append(t)

print(max(max(Array1)-min(Array1),max(Array2)-min(Array2)))
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
n=int(input())
T=[[0]*n for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  T[u-1][v-1]=w
  T[v-1][u-1]=w
d=floyd_warshall(csgraph=T, directed=False, return_predecessors=False)
for i in range(n):
  print(0 if d[0][i]%2==0 else 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
E=[]
for i in range(n-1):
  u,v,w=map(int,input().split())
  E.append([u,v,w])
def BFS(edges,N):
  roots=[[] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(0)
  dist[0]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(E,n)
for i in range(n):
  print(0 if D[i]%2==0 else 1)
### BUGGY CODE ###

#105_D
N,M=map(int,input().split())
A=list(map(int,input().split()))
S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+A[i]
S_Mod=[S[i]%M for i in range(N+1)]

cnt=0
for x in range(M):
    cnt+=S_Mod.count(x)*(S_Mod.count(x)-1)//2
print(cnt)

### FIXED CODE ###

#105_D
N,M=map(int,input().split())
A=list(map(int,input().split()))
S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+A[i]
S_Mod=[S[i]%M for i in range(N+1)]
T=sorted(S_Mod)

cnt=0
tmp=1
for i in range(N):
    if T[i]==T[i+1]:
        tmp+=1
    else:
        cnt+=tmp*(tmp-1)//2
        tmp=1
cnt+=tmp*(tmp-1)//2

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

import numpy as np
# from operator import itemgetter

n = int(input())
s = []

# for i in range(n):
#     s.append(input())

buf = []
cnt = []

for i in range(n):
    buf2 = input()
    if buf2 not in buf:
        buf.append(buf2)
        cnt.append(0)
    cnt[buf.index(buf2)] += 1

# for i in s:
#     if i not in buf:
#         buf.append(i)
#         cnt.append(0)
#     cnt[buf.index(i)] += 1

# ans = np.where(cnt == np.max(cnt))[0].tolist()
aaa = np.max(cnt)
ans2 = np.array(buf)[np.array(cnt) == aaa]

# ans = [i for i, x in enumerate(cnt) if x == max(cnt)]

# ans2 = [buf[i] for i in range(len(buf)) if i in ans]


ans3 = np.sort(ans2)

for i in ans3:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

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

#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

# N = 200 x 200 x 200 = 8000000でO(N)で計算できることから間に合うはず
import math
ans = 0
K = int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(i,math.gcd(j,k))
print(ans)






### FIXED CODE ###

#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

# N = 200 x 200 x 200 = 8000000でO(N)で計算できることから間に合うはず
import math
ans = 0
K = int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp = math.gcd(i,j)
        for k in range(1,K+1):
            ans += math.gcd(k,tmp)
print(ans)
### BUGGY CODE ###

s=list(input())
top=bool()
t=[]
u=[]
n=int(input())
for i in range(n):
  q=list(map(str,input().split()))
  if q[0]=='1':
    top=not top
  else:
    if (q[1]=="1") ^ top:
      s.insert(0,q[2])
    else:
      s.append(q[2])
if top:
  print(*list(reversed(s)),sep='')
else:
  print(*s,sep='')


### FIXED CODE ###

s=list(input())
top=bool()
t=[]
u=[]
n=int(input())
for i in range(n):
  q=list(map(str,input().split()))
  if q[0]=='1':
    top=not top
  else:
    if (q[1]=="1") ^ top:
      t.append(q[2])
    else:
      u.append(q[2])
s=list(reversed(t))+s+u
if top:
  print(*list(reversed(s)),sep='')
else:
  print(*s,sep='')
### BUGGY CODE ###

x, k, d = map(int, input().split())
x = abs(x)
while k > 0:
    x = min(abs(x + d), abs(x - d))
    k -= 1
print(x)


### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)

k_ = min(k, x // d)
k = k - k_
x = x-k_*d

if k % 2 != 0:
    x = abs(x-d)
print(x)
### BUGGY CODE ###

# coding: utf-8

n, m = map(int, input().split())
ans = [0 for _ in range(n+1)]
z = 10**9 + 7

a_list = [int(input()) for _ in range(m)]
# print(a_list)

ans[0] = 1
if 1 not in a_list:
    ans[1] = 1
else:
    ans[1] = 0
        
for i in range(2, n+1):
    if i in a_list:
        ans[i] = 0
    else:
        ans[i] += ans[i-1]+ans[i-2]
        
# print(ans)
print(int(ans[-1]%z))

### FIXED CODE ###

# coding: utf-8

n, m = map(int, input().split())
z = 10**9 + 7

ans = [1]
if m != 0:
    a_i = int(input())
else:
    a_i = 0
m_count = 1
if a_i == 1:
    ans.append(0)
    if m_count < m:
        a_i = int(input())
        m_count += 1
else:
    ans.append(1)
        
for i in range(2, n+1):
    if a_i == i:
        ans.append(0)
        if m_count < m:
            a_i = int(input())
            m_count += 1
    else:
        ans.append(ans[i-1]+ans[i-2])
        
# print(ans, ans[67])
print(int(ans[-1]%z))
### BUGGY CODE ###

n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = list(range(1, n + 1))
b = list(range(n, 0, -1))
for c, i in p:
    i -= 1
    a[i:] = map(lambda x: x + c, a[i:])
    b[:i + 1] = map(lambda x: x + c, b[:i + 1])
print(*a)
print(*b)


### FIXED CODE ###

# numpyが使えると聞いて
import numpy as np

n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = np.arange(1, n + 1)
b = np.arange(n, 0, -1)
for c, i in p:
    i -= 1
    a[i:] += c
    b[:i + 1] += c
print(*a)
print(*b)
### BUGGY CODE ###

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

A=[]
answer=0
base=0
B=[]

for i in range(K):
    sum=0
    for j in range(1,p[i]+1):
        sum+=j
    base+=sum/p[i]
    B.append(sum/p[i])
A.append(base)
for j in range(K,N):
    sum=0
    for k in range(1,p[j]+1):
        sum+=k
    B.append(sum/p[j])
    base+=sum/p[j]
    base-=B[j-K]
    A.append(base)
print(max(A))

### FIXED CODE ###

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

A=[]
base=0
B=[]

for i in range(N):
    if p[i]%2==0:
        A.append(((p[i]+1)*p[i]//2)/p[i])
    else:
        A.append((((p[i]+1)*(p[i]//2)+((p[i]+1)//2)))/p[i])
    
for l in range(K):
    base+=A[l]
B.append(base)
for k in range(K,N):
    base+=A[k]
    base-=A[k-K]
    B.append(base)    

print(max(B))
#print(A)
### BUGGY CODE ###

from math import ceil,floor
k,q=map(int,input().split())
d=list(map(int,input().split()))
for _ in range(q):
  n,x,m=map(int,input().split())
  dd=[d[i]%m for i in range(k)]
  cnt1=0
  cnt2=0
  for i in range(k):
    if dd[i]==0:
      cnt1+=ceil((n-i-1)/k)
  a=x
  for i in range(k):
    a+=ceil((n-i-1)/k)*dd[i]
  cnt2=a//m-x//m
  print(n-1-cnt1-cnt2)


### FIXED CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
d=list(map(int,input().split()))
for _ in range(q):
  n,x,m=map(int,input().split())
  dd=[d[i]%m for i in range(k)]
  for i in range(k):
    if dd[i]==0:
      dd[i]=m
  s=x%m+sum(dd)*((n-1)//k)+sum(dd[:(n-1)%k])
  print(n-1-s//m)
### BUGGY CODE ###

def comb(n):
    if n <= 1:
        return 0
    return n * (n - 1) // 2


def check(L):
    s = 0

    a = 0
    c = 0
    #print(L)
    for i in range(len(L)):
        if a != L[i]:
            s += comb(c)
            a = L[i]
            c = 1 
        else:
            c += 1
    s += comb(c)

    return s

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

for k in range(N):
    AA = list(A)
    del(AA[k])
    AA = sorted(AA)
    print(check(AA))



### FIXED CODE ###

def comb(n):
    if n <= 1:
        return 0
    return n * (n - 1) // 2


def check(L):
    r = {}
    a = 0
    c = 0
    for i in range(len(L)):
        if a != L[i]:
            if i != 0:
                r[a] = [comb(c), comb(c - 1)]
            a = L[i]
            c = 1 
        else:
            c += 1
    r[a] = [comb(c), comb(c - 1)]
    #print(r)
    return r

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

D = {}
for i in range(len(A)):
    D[i] = A[i]

D = sorted(D.items(), key=lambda x: x[1])
V = {}
for i in range(len(D)):
    V[D[i][0]] = i

AA = sorted(A)
rr = check(AA)
ss = 0
for k, v in rr.items():
    ss += v[0]
#print(ss)

for k in range(N):
    index = A[k]
    a = rr[index][0] - rr[index][1]
    print(ss - a)
### BUGGY CODE ###

s = input().split()

a = int(s[0])
b = int(s[1])
x = int(s[2])

count = 0

for num in range(a, b + 1):
    if num % x == 0:
        count += 1

print(count)

### FIXED CODE ###

s = input().split()

a = int(s[0])
b = int(s[1])
x = int(s[2])

def bet_ween(p, q):
    if p < 0:
        return 0
    else:
        return (p // q) + 1


fa = bet_ween(a-1, x)
fb = bet_ween(b, x)
answer = fb - fa
print(int(answer))
### BUGGY CODE ###

N, *L = map(int, open(0).read().split())
cost = []
for i, m in enumerate(zip(*[iter(L)]*N)):
  cost.append(list(m))
  cost[i][i] = 10**10
ans = 0
for i in range(N):
  for j in range(i):
    m = min(cost[i][k]+cost[k][j] for k in range(N))
    if m<cost[i][j]:
      print(-1)
      import sys
      sys.exit()
    if m!=cost[i][j]:
      ans += cost[i][j]
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
dist = [[0]*N for i in range(N)]
log = defaultdict(int)
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    for k in range(N):
      if cost[i][j]>=cost[i][k]+cost[k][j]:
        m = min(m,cost[i][k]+cost[k][j])
        if k != i and k!= j:
          log[(min(i,j),max(i,j))] = 1
    dist[i][j] = m
    dist[j][i] = m
ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = False
    if dist[i][j]<cost[i][j]:
      print(-1)
      flag = True
      break
    elif log[(i,j)]==0:
      ans += cost[i][j]
  if flag:
    break
else:
  print(ans)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    
    n = int(input())
    s = input()

    ans = 0
    for i in range(1, n):
        cnt = 0
        for j in range(n-i):
            if s[i+j] == s[j]:
                cnt += 1
            else:
                if cnt >= i:
                    ans = max(ans, i)
                    break
                else:
                    ans = max(ans, cnt)
                    cnt = 0

        ans = max(ans, min(cnt, i))

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

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

N=int(input())
A=[i for i in input().split()]
s=A[0]
if N%2==1:
    for i in range(1,N):
        if i%2==1:
            s=s+' '+A[i]
        else:
            s=A[i]+' ' +s
else:
    for i in range(1,N):
        if i%2==0:
            s=s+' '+A[i]
        else:
            s=s=A[i]+' ' +s
print(s)

### FIXED CODE ###

from collections import deque
N=int(input())
A=[i for i in input().split()]
s=deque()
s.append(A[0])
if N%2==1:
    for i in range(1,N):
        if i%2==1:
            s.append(A[i])
        else:
            s.appendleft(A[i])
else:
    for i in range(1,N):
        if i%2==0:
            s.append(A[i])
        else:
            s.appendleft(A[i])
print(' '.join(map(str,s)))
### BUGGY CODE ###

n,m=map(int,input().split())
max=1
for i in range(1,m//n+1):
    if m%i==0:
        max=i
print(max)

### FIXED CODE ###

import math

n,m=map(int,input().split())
if n==1:
        print(m)
else:
        l=[]
        for i in range(1,math.floor(m**0.5)+1):
           if m%i==0 and i<=m//n:
                l.append(i)
                if m//i<=m//n:
                        l.append(m//i)
        l.sort()
        print(l[-1])
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    heights = list(map(int, input().split()))

    dp = [float('inf') for i in range(n)]
    dp[0] = 0
    for i in range(1, n):
        for j in range(1, k + 1):
            if i - j < 0:
                break
            dp[i] = min(dp[i], dp[i - j] + abs(heights[i] - heights[i - j]))

    print(dp[n - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    heights = list(map(int, input().split()))

    dp = [float('inf') for i in range(n)]
    dp[0] = 0
    for i in range(1, n):
        dp[i] = min(dp[j] + abs(heights[i] - heights[j]) for j in range(max(i - k, 0), i))
        # for j in range(1, k + 1):
        #     if i - j < 0:
        #         break
        #     dp[i] = min(dp[i], dp[i - j] + abs(heights[i] - heights[i - j]))

    print(dp[n - 1])


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

import sys
input = sys.stdin.readline

N,M = map(int, input().split())
full = 2**N
dp = [float("inf")]*full
dp[0] = 0

for m in range(M):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))
    num = 0
    for c in C:
        num += 2**(c-1)
    for i in range(full):
        if dp[i]!=float("inf"):
            dp[i|num] = min(dp[i|num],dp[i]+a)
print(dp[-1] if dp[-1]!=float("inf") else -1)


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N,M = map(int,input().split())
    full = 2**N
    dp = [float("inf")]*full
    dp[0] = 0


    for m in range(M):
        a,b = map(int, input().split())
        C = list(map(int, input().split()))
        #鍵mで開く宝箱を二進法で表記
        state = 0
        for c in C:
            state += 2**(c-1)

        #状態iに対して鍵mを使い、状態i|stateにいく場合と、元から入っている場合の大小を比較
        #状態i|state即ち状態iに対して鍵mを使った後の状態
        for i in range(full):
            if dp[i] != float("inf"):
                dp[i|state] = min(dp[i]+a,dp[i|state])

    if dp[-1]==float("inf"):
    #dp[-1]はdp[full-1]でも同じ
        return -1

    return dp[-1]

print(main())
### BUGGY CODE ###

from collections import defaultdict


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)

    for c in list(t):
        if c not in l.keys():
            print(-1)
            exit()

    N = 0
    current = 0
    for c in list(t):
        if current >= l[c][-1]:
            current = l[c][0]
            N += 1
            continue

        for i in l[c]:
            if current < i:
                current = i
                break

    print(N * len(s) + current)


if __name__ == '__main__':
    p_e()


### FIXED CODE ###

from collections import defaultdict
from bisect import *


def p_e():
    s = input()
    t = input()
    l = defaultdict(list)

    for i, c in enumerate(list(s)):
        l[c].append(i + 1)

    for c in list(t):
        if c not in l.keys():
            print(-1)
            exit()

    N = 0
    current = -1
    for c in list(t):
        R = l[c]

        x = bisect(R, current)

        if len(R) == x:
            N += 1
            current = R[0]
        else:
            current = R[x]

    print(N * len(s) + current)


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

import fractions
from math import sqrt

A, B = map(int, input().split())

G = fractions.gcd(A, B)
N = int(sqrt(G))+1
g = G
ans = 1

for i in range(G):
    if (g < i):
        break
    if(g % (i+2) == 0):
        ans += 1
        while(g % (i+2) == 0):
            g /= i+2

print(ans)


### FIXED CODE ###

import fractions
from math import sqrt

A, B = map(int, input().split())

G = fractions.gcd(A, B)
N = int(sqrt(max(A,B)))+1
g = G
ans = 1

for i in range(2, N+3):
    if(g % i == 0):
        ans += 1
        while(g % i == 0):
            g = g/i
            
if g != 1:
    ans += 1

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

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

s = input()

separators = [list(map(int, input().split())) for i in range(q)]

cnt = []

for separate in separators:
    current_string = s[separate[0]-1:separate[1]]

    cnt.append(current_string.count('AC'))

for i in cnt:
    print(i)


### FIXED CODE ###

# C - GeT AC
# https://abc122.contest.atcoder.jp/tasks/abc122_c

"""
累積和を用いて実装しないと時間が足りない
"""

import sys
n, q = list(map(int, sys.stdin.readline().split()))
s = list(sys.stdin.readline())

cnt = [0] * (len(s)+1)

"""
ACを数えるために受けた文字列ｓを展開して数えていく
"""

for i in range(1, len(s)):
    """
    s = ACACTACG
    cnt = [0,0,1,1,2,2,2,3,3]
    i == 1, 2, 3……len(s)
    
    i == 1
    s[i] == C s[i-1] == A
    ここで代入されるべきなのはcntのindex2番である　
        なぜならば、cntは最初に0を代入するので、s[i]の位置に当たるのはcnt[i]+1であるため
    """

    if s[i] == "C" and s[i-1] == "A":
        cnt[i+1] = cnt[i] + 1
    else:
        cnt[i+1] = cnt[i]


r_and_l = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

for e in r_and_l:
    num = e[0]
    print(cnt[e[1]] - cnt[num] )