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

def order(c):
    return 1 << (ord(c) - 97)

def count(n):
    return bin(n).count("1")

def merge(x, y):
    return x | y

def main():
    N = int(input())
    S = [x for x in input()]
    Q = int(input())
    L = 2**22
    Seg = [0]*(L*2)

    def update(k, x):
        k += L 
        Seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            Seg[k] = merge(Seg[2*k+1], Seg[2*k+2])
        Seg[0] = merge(Seg[1], Seg[2])

    def find(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            #print("find*", (a,b,k,l,r), "=",count(Seg[k]))
            return Seg[k]
        vl = find(a, b, 2*k+1, l, (l+r)//2)
        vr = find(a, b, 2*k+2, (l+r)//2, r)
        #print("find_", (a,b,k,l,r), "=",count(merge(vl, vr)))
        return merge(vl, vr)

    # read S, and update tree
    for i in range(N):
        update(i, order(S[i]))
        #print("Seg", *[count(x) for x in Seg])
    #print("Seg=", [count(x) for x in Seg])

    for _ in range(Q):
        q, i, c = input().split()
        if q == '1':
            i = int(i)-1
            if S[i] == c:
                continue
            S[i] = c
            update(i, order(S[i]))
            #print("Seg=", [count(x) for x in Seg])
        else:
            l, r = int(i), int(c)
            #print((l,r))
            print(count(find(l, r+1, 0, 0, L)))
main()


### FIXED CODE ###

import numpy as np

def count(n):
    return bin(n).count("1")

def merge(x, y):
    return x | y

def update(Seg, k, x):
    k += len(Seg)//2
    Seg[k] = x
    while k > 0:
        k = (k - 1) // 2
        Seg[k] = Seg[k*2+1]|Seg[k*2+2]

d = {c:(1 << (ord(c)-97)) for c in 'abcdefghijklmnopqrstuvwxyz'}

class SegmentTree:
    def __init__(self, A):
        N = len(A)
        n = (N-1).bit_length()
        self.N = 1 << n
        self.Seg = [0 for i in range(2*self.N)]
        #for i in range(N): self.update(i, A[i])
        if True:
            for i in range(N):
                self.Seg[self.N+i-1] = d[A[i]]
            for i in range(0,self.N-2)[::-1]:
                self.Seg[i] = self.Seg[i*2+1] | self.Seg[i*2+2]

    def update(self, k, x):
        i = self.N+k-1
        self.Seg[i] = d[x]
        while i > 0:
            i = (i-1)//2
            self.Seg[i] = self.Seg[i*2+1]|self.Seg[i*2+2]
    def merge(self, x, y):
        return x | y

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.N)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.Seg[k]
        vl = self.query_(a, b, 2*k+1, l, (l+r)//2)
        vr = self.query_(a, b, 2*k+2, (l+r)//2, r)
        return merge(vl, vr)

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input()[:-1]
    Q = int(input())
    Seg = SegmentTree(S)

    for _ in range(Q):
        q, i, c = input().split()
        if q == '1':
            i = int(i)-1
            Seg.update(i, c)
        else:
            l, r = int(i), int(c)
            print(count(Seg.query(l-1, r)))
main()
### BUGGY CODE ###

d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

def dfs(s=[], score=0):
    ans = float('inf')
    if len(s)==d:
        if score >= g:
            return sum(s)
        else:
            return float('inf')
    else:
        p, c = pc[len(s)]
        for i in range(p+1):
            a = 100*(len(s)+1)*i
            if i==p:
                a+=c
            ans = min(ans, dfs(s+[i], score+a))
    return ans

print(dfs([]))


### FIXED CODE ###

from itertools import product
from math import ceil
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = 10**9
for bit in product([0, 1], repeat=d):
    score = 0
    probs = 0
    for i, b in enumerate(bit):
        p, c = pc[i]
        if b==1:
            probs+=p
            score+=100*(i+1)*p
            score+=c
    if score >= g:
        ans = min(ans, probs)
    else:
        # greedyに足す
        for i, b in list(enumerate(bit))[::-1]:
            p, c = pc[i]
            if b==1:
                continue
            if score+100*(i+1)*p >= g:
                a = ceil((g-score)/(100*(i+1)))
                probs += a
                score += (100*(i+1))*a
                if a == p: score += c
                break
            else:
                probs += p
                score += (100*(i+1))*p+c
                if score >= g: break
        if score >= g:
            ans = min(ans, probs)
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

state = 0
for i in range(q):
    query = list(input().split())
    if query[0] == "1":
        state += 1
    else:
        if (int(query[1]) + state) % 2 == 1:
            s = query[2] + s
        else:
            s += query[2]

if state % 2 == 0:
    print(s)
else:
    s = s[::-1]
    print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

state = 0
for i in range(q):
    query = list(input().split())
    if query[0] == "1":
        state += 1
    else:
        if (int(query[1]) + state) % 2 == 1:
            s.appendleft(query[2])
        else:
            s.append(query[2])

if state % 2 == 1:
    s = list(s)[::-1]

print("".join(s))
### BUGGY CODE ###

s = input()
t = input()
len_s = len(s)

a = ord('a')
alph = [[] for _ in range(ord('z')-a+1)]
for i, c in enumerate(s):
  alph[ord(c)-a].append(i)

tmp = alph[ord(t[0])-a]
if tmp:
  idx = min(tmp)
  for c in t[1:]:
    tmp = alph[ord(c)-a]
    if tmp:
      idx += min(map(lambda x: (x - idx - 1) % len_s + 1, tmp))
    else:
      idx = -2
      break
  print(idx + 1)
else:
  print(-1)

### FIXED CODE ###

s = input()
t = input()
len_s = len(s)
a = ord('a')
dictionary = {chr(a + i): [[], 0] for i in range(26)}
for i in range(len_s):
  dictionary[s[i]][0].append(i)
  dictionary[s[i]][1] += 1
repeat = 0
cur_index = -1
for c in t:
  indices, len_indices = dictionary[c]
  if len_indices == 0:
    repeat = 0
    cur_index = -2
    break
  inf = -1
  sup = len_indices
  while sup - inf > 1:
    x = (inf + sup) // 2
    if indices[x] > cur_index:
      sup = x
    else:
      inf = x
  if sup == len_indices:
    repeat += 1
    cur_index = indices[0]
  else:
    cur_index = indices[sup]
print(len_s * repeat + cur_index + 1)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
def findb(ind,checker):
    global count
    if ind + checker < N:
        add = S[ind:ind+checker].count("B") + S[ind+checker+1:].count("B")
    else:
        add = S[ind:].count("B")
    count += add
def findg(ind,checker):
    global count
    if ind + checker < N:
        add = S[ind:ind+checker].count("G") + S[ind+checker+1:].count("G")
    else:
        add = S[ind:].count("G")
    count += add
def findr(ind,checker):
    global count
    if ind + checker < N:
        add = S[ind:ind+checker].count("R") + S[ind+checker+1:].count("R")
    else:
        add = S[ind:].count("R")
    count += add
for i in range(N):
    if S[i] == "R":
        for j in [x for x, y in enumerate(S[i:]) if y == 'G']:
            findb(i+j,j)
        for j in [x for x, y in enumerate(S[i:]) if y == 'B']:
            findg(i+j,j)
    elif S[i] == "G":
        for j in [x for x, y in enumerate(S[i:]) if y == 'B']:
            findr(i+j,j)
        for j in [x for x, y in enumerate(S[i:]) if y == 'R']:
            findb(i+j,j)
    else:
        for j in [x for x, y in enumerate(S[i:]) if y == 'R']:
            findg(i+j,j)
        for j in [x for x, y in enumerate(S[i:]) if y == 'G']:
            findr(i+j,j)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)
### BUGGY CODE ###

def main():
    a = int(input())
    b = list(map(int, input().split()))
    for i in range(1,a):
        print(b.count(i))
    print(0)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a = int(input())
    b = list(map(int, input().split()))
    c = [0]*a
    for i in b:
        c[i-1] += 1
    for j in c:
        print(j)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,s=map(int,input().split())
N=[i+1 for i in range(n)]
list1=[]
pattern=[]
A=list(map(int,input().split()))

ft=0  
dict={}
for i in range(n+1):
    dict[i]=[]
for i in range(1,2**n):
    list2=[]
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(N[j])
    pattern=[]
    for x in range(1,2**len(list2)):
        pt=[]
        for y in range(len(list2)):
            if (x>>y)&1==1:
                pt.append(list2[y])
        pattern.append(pt)
   # print(pattern)

    for p in pattern:
        sum=0
        if p in dict[len(p)]:
            ft+=1
        else:
            for x in p:
                sum+=A[x-1]
            if sum==s:
                dict[len(p)].append(p)
                ft+=1
                ft=ft%998244353
print(ft%998244353)

### FIXED CODE ###

import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    dp=np.array([0 for i in range(min(3001,s+1))])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
        dp%=998244353
    print(dp[s])
    

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

n = int(input())
a = list(map(int, input().split()))
a.sort()
ok = [True for _ in range(10**6+1)]
ans = 0
for i, x in enumerate(a):
	if ok[x]:
		if i == n-1:
			ans += 1
		elif a[i+1] != x:
			ans += 1
	for y in range(x, 10**6+1, x):
		ok[y] = False
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
num = [0 for _ in range(10**6+1)]
for x in a:
	num[x] += 1

ok = [True for _ in range(10**6+1)]
ans = 0
for i in range(1, 10**6+1):
	if num[i] == 1 and ok[i] == True:
		ans += 1
	if num[i]:
		for j in range(i, 10**6+1, i):
			ok[j] = False
print(ans)
### BUGGY CODE ###

#b
import sys
def input(): return sys.stdin.readline().strip()
n = int(input())
s = [input() for _ in range(n)]
s.sort(key=len)
ans = 0
trie = {'!': True}
for si in s:
    cursor = trie
    si = list(si)
    while True:
        for nextchar in cursor:
            if nextchar == '!':
                continue
            if '!' in cursor[nextchar] and nextchar in si:
                ans += 1
        popchar = si.pop(-1)
        if popchar in cursor:
            cursor = cursor[popchar]
        else:
            cursor[popchar] = {}
            cursor = cursor[popchar]
            for popchar in reversed(si):
                cursor[popchar] = {}
                cursor = cursor[popchar]
            cursor['!'] = True
            break
print(ans)

### FIXED CODE ###

#b（直し）
class TrieNode:
    def __init__(self):
        self.parent = None
        self.children = {}
    def new_child(self, key):
        self.children[key] = TrieNode()
        self.children[key].parent = self
        self.children[key].label = key
        return self.children[key]

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

n = int(input())
s = [input() for _ in range(n)]
ans = -n # (Si, Si)
trie = TrieNode()
ends = set()

#build the trie
for si in s:
    cursor = trie
    for char in reversed(si):
        if char in cursor.children:
            cursor = cursor.children[char]
        else:
            cursor = cursor.new_child(char)
    else:
        ends.add(cursor)

#climb up the trie
for cursor in ends:
    head = set()
    while cursor.parent is not None:
        head.add(cursor.label)
        cursor = cursor.parent
        for char in cursor.children:
            if cursor.children[char] in ends and char in head:
                ans += 1
print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
ma = sum(p[0:K])
answer = 0
for i in range(K):
  answer += (p[i]+1)/2 
for i in range(N-K):
  newma = sum(p[i+1:K+i+1])
  if ma < newma:
    ma = newma
    answer = 0
    for j in range(K):
      answer += (p[i+1+j]+1)/2 
print(answer)
   

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
ma = sum(p[0:K]) 
newma = ma
for i in range(N-K):
  newma = newma + p[K+i] - p[i]
  if ma < newma:
    ma = newma
print((ma+K)/2)
### BUGGY CODE ###

import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][sw]-cnt[g[i]][sw-1]-cnt[g[i-1]][sw]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+2
                    j=w
                    break            
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][sw]-cnt[g[i]][sw-1]-cnt[g[i-1]][sw]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+2
                    j=w
                    break            
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

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

from sys import stdin
k = int(stdin.readline().rstrip())
num = 7
flag = 0
for i in range(1, k + 1):
    if num % k == 0:
        flag = 1
        break
    num = num * 10 + 7
if flag == 1:
    print(i)
else:
    print(-1)

### FIXED CODE ###

import sys
k = int(input())
seven = 7
ans = -1
if k % 2 == 0 or k % 5 == 0:
    print(-1)
    sys.exit()
for cnt in range(1, 10**6):
    if seven % k == 0:
        ans = cnt
        break
    seven *= 10
    seven = (seven + 7) % k
print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    lis = ''
    for i in range(n):
        lis = lis + input() + '\t'
    print(len(list(set(lis.rstrip('\t').split('\t')))))

### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    print(len(set(input().rstrip('\n') for _ in range(n))))
### BUGGY CODE ###

n, k = map(lambda x: int(x), input().split(" "))
Ps = list(map(lambda x: int(x), input().split(" ")))

result = 0
expected_list = []
for p in Ps:
    temp = sum(range(1, p+1)) / p
    expected_list.append(temp)

for i in range(n-k+1):
    temp = expected_list[i:i+k]
    temp = sum(temp)
    result = max(result, temp)

print(result)

### FIXED CODE ###

n, k = map(lambda x: int(x), input().split(" "))
Ps = list(map(lambda x: int(x), input().split(" ")))

result = 0
expected_list = []
temp_result = 0
for i, p in enumerate(Ps):
    temp = (p * (p + 1) / 2 )/ p
    expected_list.append(temp)
    temp_result += temp
    if i+1 >= k:
        result = max(result, temp_result)
        temp_result -= expected_list[i-k+1]

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

import sys
finput = sys.stdin.readline
n,m = map(int, finput().split())

tasks = [0]*n
rewards = [0]*n
total = [0]*(m+1)

for i in range(n):
    tasks[i],rewards[i] = [int(j) for j in finput().split()]

que = [idx for idx, item in enumerate(rewards) if item == max(rewards)]

day = 0

while que:
    subtasks = [tasks[i] for i in que]
    while subtasks:
        t = max(subtasks)
        idx = subtasks.index(t)
        if t+day <= m:
            total[t+day:m+1] = [total[i]+rewards[que[idx]] for i in range(t+day,m+1)]
            day += 1
        del subtasks[idx]
        del tasks[que[idx]]
        del rewards[que[idx]]
        del que[idx]
    if rewards==[]:
        break
    que += [idx for idx, item in enumerate(rewards) if item == max(rewards)]

print(max(total))


### FIXED CODE ###

import heapq
import sys

finput = sys.stdin.readline

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

q = [[] for i in range(m)]

for i in range(n):
    a,b = [int(j) for j in finput().split()]
    if a>m:
        continue
    q[a-1].append(-b)

hq = []
heapq.heapify(hq)
ans = 0
for i in range(m):
    if len(hq)==0 and len(q[i])==0:
        continue
    for j in range(len(q[i])):
        heapq.heappush(hq, q[i][j])
    ans += heapq.heappop(hq)

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

#Input
N,A,B= map(int, input().split())

#Process
cnt = 0
Ans = 0
flag_AB = True 
while cnt < N:
    if(flag_AB):
        flag_AB = False
        if(cnt + A < N):
            Ans = Ans + A
        else:
            Ans = Ans + A - (cnt + A - N)
        cnt = cnt + A
    else:
        flag_AB = True
        cnt = cnt + B

#Output
print(Ans)

### FIXED CODE ###

#Input
N,A,B= map(int, input().split())

#Process
nokori = 0
na = int(N / (A + B))
if((A+B)*na + A > N):
    nokori = N % (A + B)
else:
    nokori = A
Ans = A * na + nokori

#Output
print(Ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
count=0
answer=0

for i in range(len(A)):
  count+=A[i]
  B.append(count)
  if count==0:
    answer+=1

for i in range(len(B)-1):
  x=A[i]
  for j in range(i+1,len(B)):
   B[j]-=x
   if B[j]==0:
      answer+=1

print(answer)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0]
total=0
count=1
answer=0

for i in range(len(A)):
  total+=A[i]
  B.append(total) #iまでの部分和

B.sort() #部分和が同じ部分の数を数えると解ける
for i in range(1,len(B)):
  if B[i]==B[i-1]:
    count+=1
  else:
    answer+=count*(count-1)/2 #部分和が同じものを2個取り出す組み合わせ
    count=1
answer+=count*(count-1)/2
    
print(int(answer))
### BUGGY CODE ###

s=input()
N=len(s)
kyonen=2019
modlist=[]
for i in range(N):
    modlist.append(int(s[i:N])%kyonen)
modlist.sort()
now=modlist[0]
nowc=1
ans=0
if modlist[0]==0:
    ans+=1
for i in range(1,N):
    if modlist[i]==0:
        ans+=1
    if modlist[i]==now:
        nowc+=1
    else:
        if nowc>=2:
            ans+=int(nowc*(nowc-1)/2)
        nowc=1
        now=modlist[i]

if nowc>=2:
    ans+=int(nowc*(nowc-1)/2)

print(ans)

### FIXED CODE ###

s=input()
N=len(s)
kyonen=2019
ans=0

#alistつくる
alist=[]
for i in reversed(range(N)):
    alist.append((int(s[i])*pow(10,(N-1-i),kyonen))%kyonen)

#累積和とる
ruisekiwa=[0]
for i in range(N):
    ruisekiwa.append((ruisekiwa[-1]+alist[i])%kyonen)

#累積和リストの中から、同じ数字の組み合わせの個数を求める
kazoe=[0]*2019
for i in range(N+1):
    kazoe[ruisekiwa[i]]+=1

for i in range(2019):
    if kazoe[i]>=2:
        ans+=int(kazoe[i]*(kazoe[i]-1)/2)

if ruisekiwa[N]==0:
    ans+=1

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

from math import log2

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

maxdig = 60

ans = 0
for i in range(60, -1, -1):
  d = 2**i
  cnt1 = 0
  for j in range(N):
    if A[j]//d > 0:
      cnt1 += 1
      A[j] -= d
  ans += (cnt1*(N-cnt1)*d)
  ans = ans%1000000007

print(ans)

### FIXED CODE ###

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

maxdig = 60
mod = 10**9+7

ans = 0
for i in range(60+1):
  cnt1 = sum([1 for a in A if (a >> i) & 1])
  ans += (cnt1*(N-cnt1)*(1<<i))
  ans = ans%mod

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

import sys, string
alpha = 'abcdefghijklmnopqrstuvwxyza'
t = string.maketrans(alpha[:-1], alpha[1:])
for s in sys.stdin:
  while not('the' in s or 'this' in s or 'than' in s):
    s = s.translate(t)
  print s[:-1]

### FIXED CODE ###

import sys, string
alpha = 'abcdefghijklmnopqrstuvwxyza'
tbl = string.maketrans(alpha[:-1], alpha[1:])
for s in sys.stdin:
  while not('the' in s or 'this' in s or 'that' in s):
    s = s.translate(tbl)
  print s[:-1]
### BUGGY CODE ###

n = int(input())
s = input()
seq = list(set(list(s)))
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
ans = []
for a in range(len(genkai_list)):
    for i in range(len(s)):
        if s[i] == genkai_list[a][0]:
            for j in range(i + 1, len(s)):
                if s[j] == genkai_list[a][1]:
                    for k in range(j + 1, len(s)):
                        if s[k] == genkai_list[a][2]:
                            ans.append(a)
                            break # break1
                    else:  # break1されなかった場合
                        continue
            else:
                continue # jのループが全部回った（2文字目で一致しなかった）ら、iを次の文字に
            break
    else:
        continue # iのループが全部回った（1文字目で一致しなかった）ら、aを次の文字に
    break
print(len(set(ans)))

### FIXED CODE ###

n = int(input())
s = list(input())
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
count = 0
for a in genkai_list:
    try:
        s_ = s[s.index(a[0])+1:]
        s__ = s_[s_.index(a[1])+1:]
        if a[2] in s__:
            count += 1
    except:
        continue
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: (x[0], x[1]))

INF = 10**20
dp = [INF for i in range(H + 1)]
dp[0] = 0
for i in range(1, H + 1):
    if dp[i] != INF:
        continue
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = i - damage
        if parent <= 0:
            new_cost = mp_cost
        else:
            new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp[i] = min_mp_cost
print(dp[-1])


### FIXED CODE ###

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])