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

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

num=[0]*N

for i in range(N-1):
  if S[i:i+2]=='AC':
    num[i]=1
    
num=[0]+num+[0]
    
for i in range(Q):
  l, r=map(int, input().split())
  print(sum(num[l:r]))

### FIXED CODE ###

N, Q=map(int, input().split())
S=input()
counter=[0]*N
for i in range(N-1):
  if S[i:i+2]=='AC':
    counter[i]+=1
    
  counter[i+1]=counter[i]

counter=[0]+counter
for i in range(Q):
  l, r=map(int, input().split())
  print(counter[r-1]-counter[l-1])
### BUGGY CODE ###

N = int(input())
S = input()

ans=99999999
for i in range(len(S)+1):
    temp = S[:i].count('#') + S[i:].count('.')
    ans = min(temp, ans)
        
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
S = input()

wc = S.count('.')
bc = 0
ans = wc + bc
for s in S:
    if s == '.':
        wc -= 1
    else:
        bc += 1
    temp = wc + bc
    ans = min(temp, ans)
        
print(ans)
### BUGGY CODE ###

s=str(input())
s=list(s)
q=int(input())
temp=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    s.reverse()
  else:
    if temp[2]=="1":
      s.insert(0,temp[4])
    else:
      s.append(temp[4])
print("".join(s))

### FIXED CODE ###

s=str(input())
s=list(s)
q=int(input())
sb=[0]*(q+1)
sa=[0]*(q+1)
sbi=0
sai=0
ta=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    ta=ta+1
  else:
    if (temp[2]=="1" and ta%2==0) or (temp[2]=="2" and ta%2!=0):
      sb[sbi]=temp[4]
      sbi=sbi+1
    else:
      sa[sai]=temp[4]
      sai=sai+1
lsb=sb.index(0)
lsa=sa.index(0)
sb.reverse()
ans=sb[len(sb)-lsb:len(sb)]+s+sa[0:lsa]
if ta%2!=0:
  ans.reverse()
print("".join(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = input().rstrip("\r\n")[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        D[0] = int(S[0]) % P
        tenpow = 1
        for i in range(N):
            a = 10*tenpow % P * int(S[i]) % P
            D[i+1] = (a + D[i]) % P
            tenpow *= 10 % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        A = [0] * N
        tenpow = 1
        for i in range(N):
            A[i] = (S[i]*tenpow) % P
            tenpow *= 10
            tenpow %= P
        D = [0] * (N+1)
        for i in range(N):
            D[i+1] = (D[i] + A[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import Counter
s = list(map(int, list(input())))[::-1]
n = len(s)
c = Counter([])
c[0]+=1
t = 0
for i in range(n):
    t = (t+int(s[i])*pow(10, i))%2019
    c[t]+=1
ans = 0
for v in c.values():
    ans+=v*(v-1)//2
print(ans)

### FIXED CODE ###

s = input()

n = len(s)
c = [0]*2019
c[0]+=1
t = 0
digit = 1
for ss in s[::-1]:
    t = (t+int(ss)*digit) % 2019
    digit = (digit * 10) % 2019
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)
### BUGGY CODE ###

import itertools
N=int(input())
L=list(map(int,input().split()))
ans=0
for x in itertools.combinations(L,3):
  if x[0]<x[1]+x[2] and x[1]<x[0]+x[2] and x[2]<x[0]+x[1]:
    ans+=1
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(N-2):
  for j in range(N-i-2):        
    ans+=min(N-i-j-2,N-bisect.bisect_left(L,L[-j-1]-L[i]+1)-j-1)
print(ans)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque
from operator import mul
from functools import reduce

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

a.sort()

b = [1 for i in range(n)]

for i in range(n):
    if b[i] == 1:
        for j in range(i+1,n):
            if a[j] % a[i] == 0: b[j] = 0
            if a[j] == a[i]: b[i] = 0

print(sum(b))

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1]*(max(a) + 1)

for aa in a:
    for j in range(2*aa,len(b), aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)
### BUGGY CODE ###

import sys

H, N = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

for i in range(0, H):
    for j in range(N):
        dp[i + A[j]] = min(dp[i] + B[j], dp[i + A[j]])

print(min(dp[H:H + max_A]))


### FIXED CODE ###

import sys

H, N = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

for i in range(H):
    for j in range(N):
        dp[i + A[j]] = min(dp[i] + B[j], dp[i + A[j]])

print(min(dp[H:H + max_A]))
### BUGGY CODE ###

#TLE

#half_expo(a, n, mod) = (a**n) % mod
#繰り返し二乗法
def pow(a, n, mod):
    ans = 1
    while n > 0:
        if bin(n & 1) == bin(1):
            ans = ans * a
            ans %= mod
        a = a * a
        n = n >> 1
    return ans

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

### FIXED CODE ###

#TLE

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

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

MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

def main():
  while True:
    n = int(input())
    if not n:
      break
    
    primes_less_than_n = [i for i in primes if i <= n // 2]
    ans = 0
    for i in primes_less_than_n:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()


### FIXED CODE ###

MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

def main():
  while True:
    n = int(input())
    if not n:
      break
        
    ans = 0
    for i in primes:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()
### BUGGY CODE ###

k = int(input())
s = 7
ans = 1
while ans < 10 ** 6:
    if s % k == 0:
        print(ans)
        quit()
    s = s * 10 + 7
    ans += 1
print(-1)

### FIXED CODE ###

k = int(input())
pre = 7 % k
for i in range(1, 10 ** 6):
    if pre == 0:
        print(i)
        quit()
    pre = (pre * 10 + 7) % k
print(-1)
### BUGGY CODE ###

def countAC(s):
    counter = 0
    for i in range(len(s)):
        if i == len(s)-1:
            break
        if s[i] == 'A':
            if s[i+1] == 'C':
                counter += 1
    return counter



N,Q = (int(_) for _ in input().split())
S = input()
P = []
for i in range(Q):
    P.append((int(_) for _ in input().split()))

for i in range(Q):
    l,r = P[i]
    s = S[l-1:r]
    print(countAC(s))


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])
### BUGGY CODE ###

import sys

input=sys.stdin.readline

H,W=map(int,input().split())
A=[0 for i in range(0,H)]
B=[0 for i in range(0,H)]
for i in range(0,H):
    A[i]=list(map(int,input().split()))
for i in range(0,H):
    B[i]=list(map(int,input().split()))

C=[[0 for i in range(0,W)] for j in range(0,H)]
for i in range(0,H):
    for j in range(0,W):
        C[i][j]=abs(A[i][j]-B[i][j])

dp=[[[False for k in range(0,min(80*(i+j+1)+1,80*(H-1-i+W-1-j+1)+1))] for i in range(0,W)] for j in range(0,H)]
dp[0][0][C[0][0]]=True
for i in range(0,H):
    for j in range(0,W):
        for k in range(0,min(80*(i+j+1)+1,80*(H-1-i+W-1-j+1)+1)):
            ans=False
            if i>=1:
                if k+C[i][j]<len(dp[i-1][j]):
                    ans= ans or dp[i-1][j][k+C[i][j]]
                if abs(k-C[i][j])<len(dp[i-1][j]):
                    ans= ans or dp[i-1][j][abs(k-C[i][j])]
            if j>=1:
                if k+C[i][j]<len(dp[i][j-1]):
                    ans= ans or dp[i][j-1][k+C[i][j]]
                if abs(k-C[i][j])<len(dp[i][j-1]):
                    ans= ans or dp[i][j-1][abs(k-C[i][j])]
            if (i,j)!=(0,0):
                dp[i][j][k]=ans

ans=100
for i in range(0,80+1):
    test=100
    if dp[H-1][W-1][i]:
        test=i
    if ans>test:
        ans=test

print(ans)

### FIXED CODE ###

import sys

input=sys.stdin.readline

H,W=map(int,input().split())
A=[0 for i in range(0,H)]
B=[0 for i in range(0,H)]
for i in range(0,H):
    A[i]=list(map(int,input().split()))
for i in range(0,H):
    B[i]=list(map(int,input().split()))

C=[[0 for i in range(0,W)] for j in range(0,H)]
for i in range(0,H):
    for j in range(0,W):
        C[i][j]=abs(A[i][j]-B[i][j])

dp=[[0 for i in range(0,W)] for i in range(0,H)]
if C[0][0]!=0:
    dp[0][0]=pow(2,6400+C[0][0])+pow(2,6400-C[0][0])
else:
    dp[0][0]=pow(2,6400)
for i in range(0,H):
    for j in range(0,W):
        ans1=0
        ans2=0
        if i!=0:
            ans1=(dp[i-1][j]<<C[i][j])|(dp[i-1][j]>>C[i][j])
        if j!=0:
            ans2=(dp[i][j-1]<<C[i][j])|(dp[i][j-1]>>C[i][j])
        if (i,j)!=(0,0):
            dp[i][j]=ans1|ans2

ans=100
for i in range(0,80+1):
    test=100
    if dp[H-1][W-1]>>(6400+i) &1 ==1:
        test=i
    if ans>test:
        ans=test

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

from fractions import gcd

k=int(input())
count = 0

for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            x = gcd(i,j)
            x = gcd(x,l)
            if i==j and j==l:
                count += x
            elif i==j or j==l or l==i:
                count += x*3
            else:
                count += x*6

print(count)


### FIXED CODE ###

from fractions import gcd

k=int(input())
count = 0

g = {}
for i in range(1,k+1):
    for j in range(i,k+1):
        x = gcd(i,j)
        if i==j:
            y=1
        else:
            y=2
        if x in g:
            g[x] += y
        else:
            g[x] = y
            
for i in g:
    for j in range(1,k+1):
        x = gcd(i,j)
        count += x*g[i]
        
print(count)
### BUGGY CODE ###

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

counts = {}
for i in range(N):
    a = A[i]
    if a in counts:
        counts[a] += 1
        continue
    counts[a] = 1

# print(counts)

ans_memory = {}
for k in range(N):
    if A[k] in ans_memory:
        print(ans_memory[A[k]])
        continue

    counts_tmp = counts.copy()
    counts_tmp[A[k]] -= 1

    # print(counts_tmp)
    ans = 0
    for v in counts_tmp.values():
        ans += v * (v - 1) // 2
    ans_memory[A[k]] = ans
    print(ans)


### FIXED CODE ###

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

counts = {}
for i in range(N):
    a = A[i]
    if a in counts:
        counts[a] += 1
    else:
        counts[a] = 1

# print(counts)

ans_memory = {}
ans_memory_val = {}
for k in range(N):
    if A[k] in ans_memory:
        print(ans_memory[A[k]])
        continue
    if counts[A[k]] in ans_memory_val:
        print(ans_memory_val[counts[A[k]]])
        continue

    counts_tmp = counts.copy()
    counts_tmp[A[k]] -= 1

    # print(counts_tmp)
    ans = 0
    for v in counts_tmp.values():
        ans += v * (v - 1) // 2
    ans_memory[A[k]] = ans
    ans_memory_val[counts[A[k]]] = ans
    print(ans)
### BUGGY CODE ###

import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()
ans = 1
for i in range(N):
    b = A[:i]+A[i+1:]
    g = gcd(b, ans)
    if g > ans:
        ans = g
print(ans)


### FIXED CODE ###

import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)
### BUGGY CODE ###

MOD = int(1e9) + 7

n = int(input())
a = list(map(int, input().split()))
p = [0]*(n+10)
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        b = a[i]^a[j]
        b = b%MOD
        ans +=b
print(ans%MOD)

### FIXED CODE ###

MOD = int(1e9) + 7

n = int(input())
a = list(map(int, input().split()))
ans = 0
for b in range(60)[::-1]:
    ans <<=1
    c = sum(a[i]>>b & 1 for i in range(n))
    ans = (ans + c*(n-c))%MOD
print(ans)
### BUGGY CODE ###

S = input()
le = len(S)

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[-1] == "?" else [int(x == int(S[-1])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[-i-1] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[-i-1])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

print(dp[5])

### FIXED CODE ###

import sys

for S in sys.stdin:
    break
S = S.strip()
le = len(S)

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[-1] == "?" else [int(x == int(S[-1])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[-i-1] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[-i-1])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

print(dp[5])
### BUGGY CODE ###

def main():
    N = int(input())
    A = input().split()
    ans = A[0]
    for i in range(1, N):
        ans = (ans + " " + A[i])[::-1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N = int(input())
    A = list(map(int, input().split()))
    q = deque()
    for i in range(N):
        if (N-i) % 2 == 1:
            q.appendleft(A[i])
        else:
            q.append(A[i])
    print(" ".join(map(str, q)))


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

x=int(input())
n=100
count=0
while n<x:
    x*=1.01
    count+=1
print(count)

### FIXED CODE ###

x=int(input())
n=100
count=0
while n<x:
    n+=int(n*0.01)
    count+=1
print(count)
### BUGGY CODE ###

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

def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return collections.Counter(r)

fa = collections.Counter()
for a in A:
    fa = fa | prime_factorize(a)

ans = 0
mod = 10**9+7
for a in A:
    t = 1
    fb = fa - prime_factorize(a)
    for k, v in fb.items():
        t *= (k**v % mod)
    ans += t % mod
print(ans % mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
cm = 1
for i in range(n):
    cm = cm*a[i]//gcd(cm, a[i])
ai = sum(pow(x, mod-2, mod) for x in a)
print(int(ai*cm%mod))
### BUGGY CODE ###

s=input()
t=input()
res=[]
for i in range(0,len(s)+1):
    r=[]
    for j in range(0,len(t)+1):
        r.append(0)
    res.append(r)
    
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            res[i][j]=res[i-1][j-1]+1
        else:
            res[i][j]=max(res[i-1][j-1], res[i-1][j], res[i][j-1])
            
#print(res)
LCS=[]
S_LCS=''
for i in range(0,min(len(s),len(t))+1):
    LCS.append('')
i = len(s)
j = len(t)
index=min(len(s),len(t))+1
while i > 0 and j > 0: 
    if s[i-1] == t[j-1]:
        LCS[index-1] = s[i-1]  
        i-=1
        j-=1 
        index-=1       

    elif res[i-1][j] > res[i][j-1]: 
        i-=1 
    else:
        j-=1 
        
for i in range(0,len(LCS)):
    S_LCS+=LCS[i]

print(S_LCS)

### FIXED CODE ###

def main():
    s1, s2 = input(), input()
    n, m = len(s1), len(s2)

    dp, previous = [], []
    for i in range(n + 1):
        dp.append([0] * (m + 1))
        previous.append([0] * (m + 1))

    for row in range(1, n + 1):
        for column in range(1, m + 1):
            if s1[row - 1] == s2[column - 1]:
                dp[row][column] = 1 + dp[row - 1][column - 1]
                previous[row][column] = (row - 1, column - 1)
            else:
                dpUp = dp[row - 1][column]
                dpLeft = dp[row][column - 1]

                if dpUp > dpLeft:
                    dp[row][column] = dpUp
                    previous[row][column] = (row - 1, column)
                else:
                    dp[row][column] = dpLeft
                    previous[row][column] = (row, column - 1)

    lcs = ''
    curr = (n, m)

    while True:
        row, column = curr
        if previous[row][column] == 0: break

        if s1[row - 1] == s2[column - 1]:
            lcs = f'{s1[row - 1]}{lcs}'

        curr = previous[row][column]

    print(lcs)

main()
### BUGGY CODE ###

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


if n == k or k == 1:
    print(0)
    sys.exit()
    
def min_N(n, k):
    a = n
    while True:
        b = abs(a-k)
        if a < b:
            print(a)
            sys.exit()
        elif b == 1:
            print(1)
            sys.exit()
        a = b
    print(a)
    sys.exit()
    
min_N(n, k)

### FIXED CODE ###

import sys
n ,k = map(int, input().split())
if n == k or k == 1:
    print(0)
    sys.exit()
else:
    n %= k
print(min(n, abs(n-k)))
### BUGGY CODE ###

N = int(input())
TT=0
AA=0
for k in range(N):
    T,A = map(int,input().split())
    k=0
    for k in range(100000000000000000):
        k+=1
        if T*k>=TT and A*k>=AA:
            TT=T*k 
            AA=A*k
            break
print(TT+AA)

### FIXED CODE ###

N = int(input())
TT,AA= map(int,input().split())
for k in range(1,N):
    T,A = map(int,input().split())
    j = max((TT-1+T)//T,(AA-1+A)//A)
    TT = T*j 
    AA = A*j
        
print(TT + AA)
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(1, len(s) + 1):
        dpi = dp[i]
        dpi1 = dp[i - 1]
        for j in range(1, len(t) + 1):
            k = dpi1[j]
            if dpi[j - 1] > k:
                k = dpi[j - 1]
            if (s[i - 1] == t[j - 1]) and (dpi1[j - 1] + 1 > k):
                k = dpi1[j - 1] + 1
            dpi[j] = k
    u = []
    while i > 0 and j > 0:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        elif dp[i][j - 1] == dp[i][j]:
            j -= 1
        else:
            u.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(u[::-1]))


main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
lst = []
for x in a:
  if x in lst:
    print('NO')
    break
  lst.append(x)
else:
  print('YES')
  


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
lst = []
if len(set(a)) != len(a):
  print('NO')
else:
  print('YES')
### BUGGY CODE ###

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

import sys

input = sys.stdin.readline
R = [[]]*n
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a] = R[a] + [b]
  R[b] = R[b] + [a]
  
#print(R)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]>Dis[cur]+1 or Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

print('Yes')
for i in range(1,n):
  print(Sin[i])


### FIXED CODE ###

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

import sys

input = sys.stdin.readline
R = [[] for _ in range(n)]
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a].append(b)
  R[b].append(a)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

if min(Dis)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])
### BUGGY CODE ###

# coding: utf-8
n = int(input())
li = input().split()

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


### FIXED CODE ###

# coding: utf-8
import collections
n = int(input())
lis = input().split()
#n = 2*(10**5)
#lis= [1]*n

li = collections.Counter(lis)
for i in range(n):
    #print(li.count(str(i+1)))
    print(li[str(i+1)])