Harryxun/stf_run huggingface dataset:
import sympy

n = int(input())
ans = 1

dic = sympy.factorint(n)

cnt  = 1
ans = 0
flag = False
while True:
  for k in dic.keys():
    if dic[k] >= cnt:
      dic[k] -= cnt
      ans += 1
      flag = True
  if not flag:
    break
  cnt += 1
  flag = False

print(ans)

### FIXED CODE ###

#import sympy

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
ans = 1

#dic = sympy.factorint(n)
arr = factorization(n)

cnt  = 1
ans = 0
flag = False
while True:
  for k in arr:
    if k[1] >= cnt:
      k[1] -= cnt
      ans += 1
      flag = True
  if not flag:
    break
  cnt += 1
  flag = False

if n == 1:
  print(0)
else:
  print(ans)
from math import gcd
from functools import reduce


k = int(input())

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

k += 1
ans = 0

#for i in range(1,k):
#    for j in range(i,k):
#        #print(i,j)
#        if i == j:
#            ans += gcd(i,j)
#        else:
#            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range(1,k):
        for h in range(1,k):
            #print(i,j,h)
            ans += gcd(i,j,h)


print(ans)


### FIXED CODE ###

import math
from functools import reduce


k = int(input())

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

k += 1
ans = 0

for i in range(1,k):
    for j in range(i,k):
        #print(i,j)
        if i == j:
            ans += gcd(i,j)
        else:
            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range((i+1),k):
        for h in range((j+1),k):
            #print(i,j,h)
            ans += gcd(i,j,h)*6


print(ans)
S = input()
s = S%60
m = ((S-s)/60)%60
h = (((S-s)/60)-m)/60
print "%s:%s:%s"(h,m,s)

### FIXED CODE ###

S = input()
s = S%60
m = ((S-s)/60)%60
h = (((S-s)/60)-m)/60
print "%s:%s:%s"%(h,m,s)
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

W, H, x, y = mapint()
if x==W/2 and y==Y//2:
    print(W*H/2, 1)
else:
    print(W*H/2, 0)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

W, H, x, y = mapint()
if x==W/2 and y==H/2:
    print(W*H/2, 1)
else:
    print(W*H/2, 0)
s, t = input.split()
print(t+s)


### FIXED CODE ###

s, t = input().split()
print(t+s)
N,K=map(int,input().split())
h=list(map(int, input().split()))
h.sort(reverse=True)

for i in range(N):
    if h[i]<K :
        Ans=i
        break

print(Ans)

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int, input().split()))
h.sort(reverse=True)
Ans=N
for i in range(N):
    if h[i]<K :
        Ans=i
        break

print(Ans)
n = int(input())

a = np.zeros(n,dtype=int)
b = np.zeros(n,dtype=int)

for i in range(n):
    a[i],b[i] = map(float, input().split())

#listをsortする
if n==2:
    a0 = [a[0]]
    b0 = [b[0]]
    if a[1]>=a[0]:
        a0.append(a[1])
    else:
        a0.insert(0,a[1])
    if b[1]>=a[0]:
        b0.append(b[1])
    else:
        b0.insert(0,b[1])
else:
    a0 = [a[0]]
    b0 = [b[0]]
    if a[1]>=a[0]:
        a0.append(a[1])
    else:
        a0.insert(0,a[1])
    if b[1]>=a[0]:
        b0.append(b[1])
    else:
        b0.insert(0,b[1])    
    for i in range(2,n):
        if a[i]>=a0[len(a0)-1]:
            a0.append(a[i])
        elif a[i]<=a0[0]:
            a0.insert(0,a[i])
        else:
            for j in range(len(a0)-1):
                if a0[j]<=a[i] and a[i]<=a0[j+1]:
                    a0.insert(j+1,a[i])
        if b[i]>=b0[len(b0)-1]:
            b0.append(b[i])
        elif b[i]<=b0[0]:
            b0.insert(0,b[i])
        else:
            for j in range(len(b0)-1):
                if b0[j]<=b[i] and b[i]<=b0[j+1]:
                    b0.insert(j+1,b[i])

                    
if n%2 == 1:
    a0cen = a0[(n-1)//2]
    b0cen = b0[(n-1)//2]
    nn = b0cen - a0cen + 1
else:
    a0cen1 = a0[(n-2)//2]+a0[n//2]
    b0cen1 = b0[(n-2)//2]+b0[n//2]
    nn = int(b0cen1 -a0cen1 +1)

print(nn)           


### FIXED CODE ###

import numpy as np

        
n = int(input())

a = np.zeros(n,dtype=int)
b = np.zeros(n,dtype=int)

for i in range(n):
    a[i],b[i] = map(float, input().split())

#listをsortする
a.sort()
b.sort()
                    
if n%2 == 1:
    a0cen = a[(n-1)//2]
    b0cen = b[(n-1)//2]
    nn = b0cen - a0cen + 1
else:
    a0cen1 = a[(n-2)//2]+a[n//2]
    b0cen1 = b[(n-2)//2]+b[n//2]
    nn = int(b0cen1 -a0cen1 +1)

print(nn)
N, K = list(map(int, input().split()))
H = map(int, input().split())

cost = [0] * N
cost[0] = 0
for n in range(1, N):
  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

print(cost[-1])

#def main():
#    n, k = map(int, input().split())
#    h = list(map(int, input().split()))
#    a = [0] * n
#    a[0] = 0
#    for i in range(1, n):
#        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
#    print(a[-1])
 
#if __name__ == '__main__':
#    main()

### FIXED CODE ###

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
b = input()

if b == 'A':
    print("T")
elif b == 'C':
    print("G")
elif b == 'G':
    print("C")
else b == 'T':
    print("A")

### FIXED CODE ###

b = input()
# print(type(b))

if b == "A":
    print("T")
elif b == "C":
    print("G")
elif b == "G":
    print("C")
else:
    print("A")
<?php
	$s=fgets(STDIN);
	$a="None";
	for($c='a';$c<='z'&&strlen($c)==1;$c++){
		$f=0;
		for($i=0;$i<strlen($s);$i++)$f|=$s[$i]==$c;
		if(!$f){
			$a=$c;
			break;
		}
	}
	echo $a;


### FIXED CODE ###

s=input()
a='None'
for c in 'abcdefghijklmnopqrstuvwxyz':
    f=0
    for t in s:f|=c==t
    if not f:a=c;break
print(a)
S = input()
Sum =sum(int(i) for i in str(S))
if int(S) % Sum == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
n, m  = s.count('+'), s.count('-')
print(n-m)
li=list(map(int,input().split())).sort()
a=li.pop(-1)
k=int(input())
a=a*(2**k)
for i in li:
  a+=i
print(a)


### FIXED CODE ###

li=sorted(list(map(int,input().split())))
a=li.pop(-1)
k=int(input())
a=a*(2**k)
for i in li:
  a+=i
print(a)
a = list(map(int, input().split()))

print(a[0] * a[1] - (1 * a[0]) - (1 * a[1

### FIXED CODE ###

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

print(a[0] * a[1] - (1 * a[0]) - (1 * a[1]) + 1)
import math
a, b = map(int, input().split())
print(a * b / math.gcd(a, b))

### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    a, b = b, a

c = a
d = b
r = c // d
m = c % d

while True:
    if m == 0:
        break
    else:
        c = d
        d = m
        m = c % d

print(int(a * b / d))
q=int(input())
pn=[2]
qn=[0]*10**5+1
c=0
for i in range(1, 10**5+1,2):
    for i2 in pn:
        if i % i2 == 0:
            break
        else:
            pn.append(i)
for i in range(10**5+1):
    if (pn[i]+1)/2 in pn:
        c+=1
    qn[i]=c
for _ in range(q):
    l,r = map(int, input().split())
    print(qn[r]-qn[l-1])

### FIXED CODE ###

q = int(input())
k = 10**5+1
x = [0]*k
def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    for i in range(2, n+1):
        if prime[i]:
            for j in range(i*2, n+1, i):
                prime[j] = False
    return prime

p = sieve(k+1)
c = 0
for i in range(3, k):
    if p[i] and p[(i+1)//2]:
        c += 1
    x[i] = c

for _ in range(q):
    l, r = map(int, input().split())
    print(x[r] - x[l-1])
k=input()
a=0
b=1
for i in range(k):
  a+=b
  print(a)
  if b<(a+b)/sum(map(int,str(a+b))):
    b*=10

### FIXED CODE ###

k=int(input())
a=0
b=1
for i in range(k):
  a+=b
  print(a)
  if b<(a+b)/sum(map(int,str(a+b))):
    b*=10
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    if count > 0:
      now *= 2
      nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    
    if count >= 2:
      nowm *= 2
      nowm %= (count - 1)
  
  else:
    if count >= 1:
      now %= count
    nowp %= (count + 1)
    if count >= 2:
      nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    if count > 0:
      num += now
      num %= count
    nump += nowp
    nump %= count + 1
    if count > 1:
      numm += nowm
      numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
  if count == 0:
    nextn[i] = 0
  else:  
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      if count == 2:
        nextn[i] = 0
      else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)







### FIXED CODE ###

N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print(1)
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print(2)
      else:
        print(0)
  else:
    for i in range(N):
      if i!= N - 1:
        if X[i] == "1":
          print(0)
        else:
          print(1)
      else:
        print(2)
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)
import re
s=input()

def hoge(str):
	if(str == ""):
		return "YES"
	if(str.startswith("remaerd")):
		return hoge(re.sub('^remaerd', '', str))
	if(str.startswith("resare")):
		return hoge(re.sub('^resare', '', str))
	if(str.startswith("maerd")):
		return hoge(re.sub('^maerd', '', str))
	if(str.startswith("esare")):
		return hoge(re.sub('^esare', '', str))
	return "NO"

if(s == ""):
  print("NO")
else:
	print(hoge(s[::-1]))

### FIXED CODE ###

def main():
    S = input()

    while len(S) >= 5:
        if len(S) >= 7 and S[-7:] == "dreamer":
            S = S[:-7]
            continue

        if len(S) >= 6 and S[-6:] == "eraser":
            S = S[:-6]
            continue

        elif S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue

        else:
            break

    if len(S) == 0:
        print("YES")
    else:
        print("NO")

main()
# dict形式で既出分をもたせる
N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
x = input()
sum = 0
for i in range(x):
  if i % 3 or i % 5:
    pass
  else:
    sum += i
print(sum)
    

### FIXED CODE ###

x = int(input())
sum = 0
for i in range(x+1):
    if i % 3 == 0 or i % 5 == 0:
        pass
    else:
        sum += i
print(sum)
import sys
sys.setrecursionlimit(10**7)

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

def solve(n,k):
  cand = abs(n-k)
  if n <= cand:
    return n
  else:
    return solve(cand,k)

print(solve(N,K))

### FIXED CODE ###

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

if N % K == 0:
  print(0)
else:
  q = N // K
  d = N - K*q
  print(min(d,abs(d-K)))
n = input().split(" ")
print(int(n[0])-int(n[t])

### FIXED CODE ###

X,t=map(int,input().split())
print(max(X-t,0))
def two_anagrams(s: str, t: str) -> bool:
    '''s を並び替えた実現可能な最小の文字列 s' と t を並び替えて
    実現可能な最小の文字列 t' に関して、s' < t' が成り立てば良い。
    '''
    sn, tn = len(s), len(t)
    sd, td = sorted(s), sorted(t, reverse=True)

    idx = 0
    while idx < sn and idx < tn:
        # idx-1 番目の文字までは同じと仮定する。
        if sn[idx] < tn[idx]:
            # この場合 sn < tn が成り立つ。
            return True
        if sn[idx] == tn[idx]:
            # 次に持ち越し
            idx += 1
            continue
        if sn[idx] > tn[idx]:
            # この場合 sn > tn が成り立つ。
            return False

    # min(sn, tn) 番目まで同じ。あとは長いほうが後ろ
    return sn < tn


if __name__ == "__main__":
    s = input()
    t = input()
    yes = two_anagrams(s, t)
    print('Yes' if yes else 'No')


### FIXED CODE ###

def two_anagrams(s: str, t: str) -> bool:
    '''s を並び替えた実現可能な最小の文字列 s' と t を並び替えて
    実現可能な最小の文字列 t' に関して、s' < t' が成り立てば良い。
    '''
    sn, tn = len(s), len(t)
    sd, td = sorted(s), sorted(t, reverse=True)

    idx = 0
    while idx < sn and idx < tn:
        # idx-1 番目の文字までは同じと仮定する。
        if sd[idx] < td[idx]:
            # この場合 sn < tn が成り立つ。
            return True
        if sd[idx] == td[idx]:
            # 次に持ち越し
            idx += 1
            continue
        if sd[idx] > td[idx]:
            # この場合 sn > tn が成り立つ。
            return False

    # min(sn, tn) 番目まで同じ。あとは長いほうが後ろ
    return sn < tn


if __name__ == "__main__":
    s = input()
    t = input()
    yes = two_anagrams(s, t)
    print('Yes' if yes else 'No')
#input
N, M = map(int, input().split())
x = []
y = []
z = []
for i in range(N):
    x_temp, y_temp, z_temp = map(int, input().split())
    x.append(x_temp)
    y.append(y_temp)
    z.append(z_temp)

#output
#+++
a1 = [p+q+r for p, q, r in zip(x, y, z)]
a1 = sorted(a1, reverse = True)
b1 = np.sum(a1[:M])

#++-
a2 = [p+q-r for p, q, r in zip(x, y, z)]
a2 = sorted(a2, reverse = True)
b2 = np.sum(a2[:M])

#+-+
a3 = [p-q+r for p, q, r in zip(x, y, z)]
a3 = sorted(a3, reverse = True)
b3 = np.sum(a3[:M])

#-++
a4 = [-p+q+r for p, q, r in zip(x, y, z)]
a4 = sorted(a4, reverse = True)
b4 = np.sum(a4[:M])

#+--
a5 = [p-q-r for p, q, r in zip(x, y, z)]
a5 = sorted(a5, reverse = True)
b5 = np.sum(a5[:M])

#-+-
a6 = [-p+q-r for p, q, r in zip(x, y, z)]
a6 = sorted(a6, reverse = True)
b6 = np.sum(a6[:M])

#--+
a7 = [-p-q+r for p, q, r in zip(x, y, z)]
a7 = sorted(a7, reverse = True)
b7 = np.sum(a7[:M])

#---
a8 = [-p-q-r for p, q, r in zip(x, y, z)]
a8 = sorted(a8, reverse = True)
b8 = np.sum(a8[:M])

print(max(b1, b2, b3, b4, b5, b6, b7, b8))

### FIXED CODE ###

#input
N, M = map(int, input().split())
x = []
y = []
z = []
for i in range(N):
    x_temp, y_temp, z_temp = map(int, input().split())
    x.append(x_temp)
    y.append(y_temp)
    z.append(z_temp)

#output
#+++
a1 = [p+q+r for p, q, r in zip(x, y, z)]
a1.sort(reverse = True)
b1 = sum(a1[:M])

#++-
a2 = [p+q-r for p, q, r in zip(x, y, z)]
a2.sort(reverse = True)
b2 = sum(a2[:M])

#+-+
a3 = [p-q+r for p, q, r in zip(x, y, z)]
a3.sort(reverse = True)
b3 = sum(a3[:M])

#-++
a4 = [-p+q+r for p, q, r in zip(x, y, z)]
a4.sort(reverse = True)
b4 = sum(a4[:M])

#+--
a5 = [p-q-r for p, q, r in zip(x, y, z)]
a5.sort(reverse = True)
b5 = sum(a5[:M])

#-+-
a6 = [-p+q-r for p, q, r in zip(x, y, z)]
a6.sort(reverse = True)
b6 = sum(a6[:M])

#--+
a7 = [-p-q+r for p, q, r in zip(x, y, z)]
a7.sort(reverse = True)
b7 = sum(a7[:M])

#---
a8 = [-p-q-r for p, q, r in zip(x, y, z)]
a8.sort(reverse = True)
b8 = sum(a8[:M])

print(max(b1, b2, b3, b4, b5, b6, b7, b8))
N,M = map(int, input().split())
edge=[[] for j in range(N+1)]
x = [0] * M
y = [0] * M

#N,M=4,5
#x=[1, 1, 3, 2, 3]
#y=[2, 3, 2, 4, 4]
#edge=[[], [2, 3], [4], [2, 4], []]  

for i in range(M):
    x[i], y[i] = map(int, input().split())
    edge[x[i]].append(y[i])
dp=[-1]*(N+1)
def f(x):
    if dp[x]!=-1:
        return dp[x]
    num=0
   
    for i in edge[x]:
        num=max(num,f(i)+1)
    
    dp[x]=num
    return dp[x]
m=0
for i in range(1,N+1):
    m=max(m,f(i))
print(m)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
 
 
N, M = map(int, input().split())
 
G = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    G[x] += [y]
# print(G)
 
dp = [-1] * (N + 1)
 
 
def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	# 先にノードが存在する場合
	# ノードが存在しない場合は、cnt=0のままforをすっ飛ばす
    for m in G[n]:
        cnt = max(cnt, func(m) + 1)
    dp[n] = cnt
    return cnt
 
 
for i in range(1, N + 1):
    func(i)
 
# print(dp)
print(max(dp))
x=input();
y=x*x*x ;
print y ;
return 0;

### FIXED CODE ###

x=input();
y=x*x*x ;
print y ;
x, a, b = (int(i) for i in input().split())

if b-a <= 0: 
  print('delicious')
elif b-a <= X:
  print('safe')
else:
  print('dengerous')

### FIXED CODE ###

x, a, b = (int(i) for i in input().split())

n = b - a
if n <= 0:
  print('delicious')
elif n <= x:
  print('safe')
else:
  print('dangerous')
N, K = map(int, input().split())
def dif(n, k):
    if abs(n - k) <= n:
        return dif(abs(n-k), k)
    else:
        return n

print(dif(N,K))

### FIXED CODE ###

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

def dif(n, k):
    if abs(n - k) <= n:
        return dif(abs(n-k), k)
    else:
        return n

if N % K == 0:
    print(0)
else:
    N = N % K
    print(dif(N,K))
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import math
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()

n=2**(int(math.log2(n))+1)

t=[set([]) for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  if r<=a or b<=l:
     if b==l:
         return t[k]
     return set([])
  elif a<=l and r<=b:
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,set([s[i]]))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,set([c]))
 else:
   c=int(c)
   if i==c:
     print(1)
   else:
     print(len(qr(i-1,c-1,0,0,n)))
   
 q-=1


### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()
N=0
while n:
  n>>=1
  N+=1
n=2**N

t=[0 for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return 0
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,1<<(ord(s[i])-ord("a")))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,1<<(ord(c)-ord("a")))
 else:
   c=int(c)
   x=0
   z=qr(i-1,c,0,0,n)
   while z:
     if z%2==1:
        x+=1
     z>>=1
   print(x)
 q-=1
import collections
n,m = map(int,input().split())
a = list(map(int,input().split()))
col = collections.Counter(a)
 
for i in range(m):
  b,c = map(int,input().split())
  col[c] += b
col = sorted(col.items(), key=lambda x:x[0],reverse=True)
 
ans=0
for k,v in col:
  if n <= v:
    ans += k*n
    break
  else:
    ans += k*v
    n -= v
print(ans)

### FIXED CODE ###

import collections
n,m = map(int,input().split())
a = list(map(int,input().split()))
col = collections.Counter(a)
 
for i in range(m):
  b,c = map(int,input().split())
  col[c] += b
col = sorted(col.items(), key=lambda x:x[0],reverse=True)
 
ans=0
for k,v in col:
  if n <= v:
    ans += k*n
    break
  else:
    ans += k*v
    n -= v
print(ans)
n = int(input())
otoshidama = {JPY:0, BTC:0}
for i in range(n):
    a, b = map(str, input().split())
    a = float(a)
    if b == JPY:
        otoshidama[JPY] = otoshidama[JPY] + a
    else:
        otoshidama[BTC] = otoshidama[BTC] + a
ans = otochidama[JPY] + otochidama[BTC] * 380000.0
print(ans)

### FIXED CODE ###

N = int(input())
x = [0]*N
u = [0]*N
answer = 0
for i in range(N):
    x[i], u[i] = map(str, input().split())
    if u[i] == "JPY":
        answer += int(x[i])
    else:
        answer += (float(x[i]) * 380000)



print(answer)
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))


### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))
from heapq import *

n, m, s = map(int, input().split())
tree = [[] for _i in range(n+1)]
for _i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u].append([v, a, b])
    tree[v].append([u, a, b])

cd = [[0,0]]
for _i in range(n):
    cd.append(list(map(int, input().split())))

dp = [[float('inf') for _i in range(50*n+1)] for _j in range(n+1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
visit = [[-1 for _i in range(50*n+1)] for _j in range(n+1)]
while hq:
    t, p, g = heappop(hq)

    if g+cd[p][0] <= 50*n:
        x, y = t+cd[p][1], min([g+cd[p][0], 50*n])
        if dp[p][y] > x:
            dp[p][y] = x
            heappush(hq, [x, p, y])
    for x, y, z in tree[p]:
        if g-y >= 0 and dp[x][g-y] > t+z:
            dp[x][g-y] = t+z
            heappush(hq, [t+z, x, g-y])

for i in dp[2:]:
    print(min(i))

### FIXED CODE ###

from heapq import *

n, m, s = map(int, input().split())
s = min([s, 50*n])
tree = [[] for _i in range(n+1)]
for _i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u].append([v, a, b])
    tree[v].append([u, a, b])

cd = [[0,0]]
for _i in range(n):
    cd.append(list(map(int, input().split())))

dp = [[float('inf') for _i in range(50*n+1)] for _j in range(n+1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
while hq:
    t, p, g = heappop(hq)
    if g+cd[p][0] <= 50*n:
        x, y = t+cd[p][1], min([g+cd[p][0], 50*n])
        if dp[p][y] > x:
            dp[p][y] = x
            heappush(hq, [x, p, y])
    for x, y, z in tree[p]:
        if g-y >= 0 and dp[x][g-y] > t+z:
            dp[x][g-y] = t+z
            heappush(hq, [t+z, x, g-y])

for i in dp[2:]:
    print(min(i))