Harryxun/stf_run huggingface dataset:
N = int(input())
ans = 0

#奇数判定
for i in range(1, N+1, 2):
    cnt = 0
    #約数判定
    for j in range(1, i+1):
        if j % i == 0:
            cnt += 1
        if cnt == 8:
            ans += 1

print(ans)
        



### FIXED CODE ###

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

print((A-1) * (B-1))
N, M = map( int, input().split() )
a = list( map( int, input().split() ) )
 
d = []
for i in range( M ):
  b, c = map( int, input().split() )
  d += [ c ] * b
d.sort()
a += d
a.sort()
print(sum(a[-N:]))

### FIXED CODE ###

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

price = b
if ( 6 <= a ) & ( a <= 12 ):
  price //=2
elif ( a < 6 ):
  price = 0

print(price)
from collections import defaultdict

visited = [False for _ in range(100001)]


def dfs(p: int, n: int, h: list, ways: dict, result: dict):
    if visited[p]:
        return
    
    visited[p] = True
    result[h[p-1]] += 1

    for w in ways[p]:
        dfs(w, n, h, ways, result)


def main():
    tmp = [int(i) for i in input().split()]
    n = tmp[0]
    m = tmp[1]

    ways = defaultdict(set)
    h = [int(i) for i in input().split()]
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        ways[tmp[0]].add(tmp[1])
        ways[tmp[1]].add(tmp[0])
    
    cnt = 0
    for i in range(1, n+1):
        result = defaultdict(int)
        dfs(i, n, h, ways, result)
        if len(result) > 0:
            h_max = max(list(result.keys()))
            cnt += result[h_max]
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict

def check(p: int, h: list, ways: dict):
    for w in ways[p]:
        if h[p] <= h[w]:
            return False
    return True


def main():
    tmp = [int(i) for i in input().split()]
    n = tmp[0]
    m = tmp[1]

    ways = defaultdict(set)
    h = [0] + [int(i) for i in input().split()]
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        ways[tmp[0]].add(tmp[1])
        ways[tmp[1]].add(tmp[0])
    
    cnt = 0
    for i in range(1, n+1):
        if check(i, h, ways):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(len(a)):
    b.append((a[i]+1)/2)
for i in range(len(a)-k+1):
    sum=0
    for j in range(i,i+k):
        sum+=b[j]
    if max<=sum:
        max=sum
print(max)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
smax=0
for i in range(k-1,n):
    if i==k-1:
        sumnow=sum(a[:i+1])
    else:
        sumnow+=a[i]-a[i-k]
    smax=max(smax,sumnow)
print((smax+k)/2)
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[0 for i in range(5)] for j in range(L+1)]

def cost(s, i, A):
    if s == 0 or s == 4:
        return A[i]
    elif s == 1 or s == 3:
        if A[i] > 0:
            if A[i]%2 == 0:
                return 0
            else:
                return 1
        else:
            return 2
    else:
        if A[i]%2 == 1:
            return 0
        else:
            return 1

for i in range(L):
    DP[i+1][0] = DP[i][0] + cost(0, i, A)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A)



print(min(DP[L]))

### FIXED CODE ###

N, K = map(int, input().split())
if K <=(N+1)//2:
  print("YES")
else:
  print("NO")
def move(str):
    returnR = 0
    returnL = 0
    cntR = str.count("R")
    cntL = str.count("L")
    if cntR%2 == 0:
        returnL += cntR//2
        returnR += cntR//2
    else:
        returnL += cntR//2
        returnR += cntR//2 + 1
        
    if cntL%2 == 0:
        returnR += cntL//2
        returnL += cntL//2
    else:
        returnR += cntL//2 
        returnL += cntL//2 + 1

    for i in range(cntR-1):
        print(0+" ",end="")
    print(returnR,end="")

    print(returnL,end="")
    for i in range(cntL-1):
        print(0+" ",end="")

    
s = input()
listS = []

while s.find("LR") > 0:
    listS.append(s[:s.find("LR")+1])
    s=s[s.find("LR")+1:]
listS.append(s)

for s in listS:
    move(s)

### FIXED CODE ###

def move(s):
    returnR = 0
    returnL = 0
    cntR = s.count("R")
    cntL = s.count("L")
    if cntR%2 == 0:
        returnL += cntR//2
        returnR += cntR//2
    else:
        returnL += cntR//2
        returnR += cntR//2 + 1
        
    if cntL%2 == 0:
        returnR += cntL//2
        returnL += cntL//2
    else:
        returnR += cntL//2 
        returnL += cntL//2 + 1

    for i in range(cntR-1):
        print("0"+" ",end="")
    print(str(returnR)+" ",end="")

    print(str(returnL)+" ",end="")
    for i in range(cntL-1):
        print("0"+" ",end="")

    
s = input()
listS = []

while s.find("LR") > 0:
    listS.append(s[:s.find("LR")+1])
    s=s[s.find("LR")+1:]
listS.append(s)

for s in listS:
    move(s)
N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N):
    sum = 0
    for j in range(M):
        sum += A[i - 1][j - 1] * B[j - 1]
    if sum > - C:
        ans += 1
print(ans)


### FIXED CODE ###

H, W = list(map(int, input().split()))
h, w = list(map(int, input().split()))
print(H*W - h*W - H*w + h*w)
# ｎとｍの取得
data = input().split()
n = int(data[0]) #n == 人数
m = int(data[1]) #m == 数字の種類
ans = 0
#ｎ回データを取得してカウント

j = 1 #j == 好きな数字
i = 1 #i == 行数カウンタ
c = [0] * (m +1)#c == ある数が含まれているかのカウンタ　0で初期化
    #データの取得

while i <= n:
    tmp = [int(s) for s in input().split()]
    td = tmp[1:] #td == 好きな番号
    tn = tmp[0]  #tn == 好きな番号の数
    
    # 数字が含まれているかの比較
    while j <= m: # jがすべての数字について実行
        
        if j in td: # jがｔｄに含まれるかの分岐
            j = int(j) #　ｊを数値に戻す
            
            c[j] += 1 # ｃのｊ番目の要素にカウント
        j = int(j) #if ではじかれたとき用にｊを数値に戻す
        j += 1# ｊをカウント
    j = 1    
    i += 1 # iをカウント

# 全てに含まれている数字の集計

for x in c:
    if x == n:
        ans += 1



print(ans)


### FIXED CODE ###

data = input().split()
a = int(data[0])
b = int(data[1])

if b%a == 0:
  print(a+b)
else:
  print(b-a)
import math

while True:
	try:
		a, b = map(int, input().split())
		print(int(math.log10(a + b, 10)) + 1)
	except EOFError:
		break

### FIXED CODE ###

import math

while True:
	try:
		a, b = map(int, input().split())
		print(int(math.log10(a + b)) + 1)
	except EOFError:
		break
from collections import Counter

N = int(raw_input())
O = list(map(int, raw_input().split()))

cnt = Counter(O)
cnt = dict(cnt)

for k in cnt:
    if cnt[k] == 1:
        del cnt[k]

for i in O:
    cnt[i] = cnt.get(i, 1) - 1
    res = 0

    for k in cnt:
        if cnt[k] >=2:
            res += (cnt[k]*(cnt[k]-1))/2
    print(res)

    cnt[i] += 1

### FIXED CODE ###

N = int(raw_input())
A = map(int, raw_input().split())
 
count = [0]*(N+2)
for i in range(N):
    id = A[i]
    count[id] = count[id]+1
 
sumN = long(0)
for i in range(N+1):
    sumN = sumN + long(long(count[i]*(count[i]-1))/2)
 
for i in range(N):
    id = A[i]
    sumz = sumN - (count[id] - 1)
    print(sumz)
S = str(input())
K = int(input())

# now_s = S[0]
# for i in range(1, len(S)):
#     if now_s == S[i]:
#         cnt += 1
#     now_s = S[i]

cnt = 0
ruisekiwa = [1]
now_s = S[0]
for i in range(1, len(S)):
    if now_s == S[i]:
        ruisekiwa[-1] += 1
    else:
        ruisekiwa.append(1)
    now_s = S[i]

for i in range(len(ruisekiwa)):
    cnt += ruisekiwa[i]//2

cnt = cnt * K

if S[0] == S[-1] and S[-2] != S[-1]:
    cnt += K-1

print(cnt)


### FIXED CODE ###

S = str(input())
K = int(input())

# now_s = S[0]
# for i in range(1, len(S)):
#     if now_s == S[i]:
#         cnt += 1
#     now_s = S[i]

if len(S) == 1:
    print(K//2)
    exit()


cnt = 0
ruisekiwa = [1]
now_s = S[0]
for i in range(1, len(S)):
    if now_s == S[i]:
        ruisekiwa[-1] += 1
    else:
        ruisekiwa.append(1)
    now_s = S[i]

if len(ruisekiwa) == 1:
    if ruisekiwa[0] % 2 == 0:
        print(ruisekiwa[0]//2*K)
        exit()

    # 文字数が奇数
    if K % 2 == 0:
        cnt += (ruisekiwa[0]//2 + 1) * (K//2)
        cnt += (ruisekiwa[0]//2) * (K//2)
    else:
        cnt += (ruisekiwa[0]//2) * (K//2 + 1)
        cnt += (ruisekiwa[0]//2 + 1) * (K//2)
    print(cnt)
    exit()



cnt = 0
for i in range(len(ruisekiwa)):
    cnt += ruisekiwa[i]//2

# 先頭と末尾が違うなら問題ない
if S[0] != S[-1]:
    print(cnt*K)
    exit()




# 先頭と末尾が同じ場合を考える

# 先頭が偶数, 末尾も偶数回数
if ruisekiwa[0] % 2 == 0 and ruisekiwa[-1] % 2 == 0:
    print(cnt * K)
    exit()
# 先頭が偶数, 末尾が奇数
if ruisekiwa[0] % 2 == 0 and ruisekiwa[-1] % 2 == 1:
    print(cnt * K)
    exit()
# 末尾が偶数なら末尾を変えれるから嬉しい
# 先頭が奇数, 末尾が偶数
if ruisekiwa[0] % 2 == 1 and ruisekiwa[-1] % 2 == 0:
    print(cnt * K)
    exit()

# 偶は先頭を変える必要があるから、嬉しい

# 先頭が奇数回数続いていて, 末尾も奇数回数
if ruisekiwa[0] % 2 == 1 and ruisekiwa[-1] % 2 == 1:
    # if K % 2 == 1:
    #     print(cnt * (K//2+1) + (cnt+1) * (K//2))
    # else:
    #     print(cnt * (K//2) + (cnt+1) * (K//2))
    # exit()
    print((cnt+1) * K -1)
    exit()
    # ここを直した, waが減った
from collections import Counter
 
n, m = map(int, input().split())
A = list(map(int, input().split()))
 
B = [0] * (n + 1)
 
for i in range(n):
  B[i + 1] = accr[i] + A[i] # BはAの累積和

li = [i % m for i in B] # それをMで割った余りがli

C = Counter(li) # 余りが同じものの個数が2つ以上ある際、その2つの組み合わせによって、割り切れる和の組み合わせ個数が求まる

ans = 0
for v in C.values():
  if v > 1:
    ans += v * (v - 1) // 2
 
print(ans)

### FIXED CODE ###

from collections import Counter
 
n, m = map(int, input().split())
A = list(map(int, input().split()))
 
B = [0] * (n + 1)
 
for i in range(n):
  B[i + 1] = B[i] + A[i] # BはAの累積和

li = [i % m for i in B] # それをMで割った余りがli

C = Counter(li) # 余りが同じものの個数が2つ以上ある際、その2つの組み合わせによって、割り切れる和の組み合わせ個数が求まる

ans = 0
for v in C.values():
  if v > 1:
    ans += v * (v - 1) // 2
 
print(ans)
N = int(input())
P = list(map(int,input().split()))

res = [False for x in range(N)]
for i in range(1,N):
  if P[i-1] >= P[i] :
    res[i] = True

print(int(sum(res)+1))

### FIXED CODE ###

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

ab = str(a) *b
ba = str(b) *a

print(min([ab,ba]))
a,p=map(int(input().split()))
x=3*a+p
print(x//2)

### FIXED CODE ###

a,p=map(int,input().split())
x=3*a+p
print(x//2)
list = input().split()

print(list[0]/list[1])

### FIXED CODE ###

list = input().split()
print(float(list[0])/float(list[1]))
n,m=map(int,input().split())
for i in range(n):
    k,*a=list(map(int,input().split()))
    b=a[0]
    for j in range(k):
        b=b-a[j]
        print(len(b))
    
    


### FIXED CODE ###

n,m=map(int,input().split())
s=set(range(1,m+1))
for i in range(n):
    k,*a=list(map(int,input().split()))
    s&=set(a)
print(len(s))
a,b=map(int.input(),split())
if a-b＊2>=0:
  print(a-b＊2)
else:
  print(0)
  


### FIXED CODE ###

a,b=map(int,input().split())
if a-b*2<=0:
  
  print(0)
else:
  print(a-b*2)
h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#": b[i*w+j] = 0; c.append(i*w+j)
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != w-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))

### FIXED CODE ###

h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#": b[i*w+j] = 0; c.append(i*w+j)
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != h-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))
S,T = list(map(str,input().split()))
ans = []
for i in range(len(S)):
    ans.append(S[i])
    ans.append(T[i])
print(''.join(ans))

### FIXED CODE ###

N = int(input())
S,T = list(map(str,input().split()))
ans = []
for i in range(len(S)):
    ans.append(S[i])
    ans.append(T[i])
print(''.join(ans))
a,b,h = map(int,input().split())

print((a+b)*h//2)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())

print((a+b)*c//2)
L, R = map(int, input().split())

P = 2019

def mul(a, b):
    return ((a % P) * (b % P)) % P

R = min(R, l+4038)

tmp = 10**9
for i in range(L, R):
    for j in range(L+1, R+1):
        tmp = min(mul(i, j), tmp)
        
print(tmp)

### FIXED CODE ###

L, R = map(int, input().split())

P = 2019

R = min(R, L+673)

tmp = 2018
for i in range(L, R):
    for j in range(L+1, R+1):
        tmp = min((i*j)%P, tmp)
        
print(tmp)
import sys
stdin = sys.stdin
from itertools import accumulate

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

n = ni()
h = na()
f = h[0]
b = False
for hi in h[1:]:
    if hi > f:
        f = hi
        b = False
    elif hi == f - 1 and not b:
        f = hi
        b = True
    elif hi == f:
        b = True
    else:
        print("No")
        quit()
print("Yes")

### FIXED CODE ###

from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, groupby
from math import floor, ceil, sqrt, factorial, log
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
from itertools import product
import sys
stdin = sys.stdin
mod = 10**9 + 7


def ns(): return stdin.readline().rstrip()


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


a, b, c = na()
print(max(b + c - a, 0))
N= input()
F = 0
for i in range(8):
  F += int(N[i])
if int(N)%F== 0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N= int(input())
F = 0
t = N
for i in range(9):
  a = N // (10**(8-i))
  F += a
  N = N - a*(10**(8-i))
if t % F== 0:
  print("Yes")
else:
  print("No")
n,m = map(int,input().split())
t = [0 for i in range(n)]
b = ""
a = True
for i in range(m):
    s,c = map(int,input().split())
    if t[s-1] != 0 and c == 0:
        a=False
    elif t[s-1] == 0 or t[s-1] == c:
        t[s-1] = c
    else:
        a=False
for i in range(n):
    b += str(t[i])
if n > 1 and b[0] == '0':
    b[0]=1
    print(b)
elif b[0] == '0':
    print(0)
elif a:
    print(b)
else:
    print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
t = [0 for i in range(n)]
e = [True for i in range(n)]
b = ""
a = False
for i in range(m):
    s,c = map(int,input().split())
    if e[s-1]:
        if s == 1 and c == 0:
            a = True
            if n == 1:
                print(0)
                exit()
        else:
            t[s-1] = c
            e[s-1] = False
    else:
        if t[s-1] != c:
            a = True
for i in range(n):
    b += str(t[i])
if a:
    print(-1)
elif n > 1 and b[0] == '0':
    print(str(1)+b[1:3])
else:
    print(b)
c1,c2 = map(str, input(),split())
c1 = list(c1)[::-1]
c2 = list(c2)
if c1 == c2:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

c1 = str(input())
c2 = str(input())
c1 = list(c1)[::-1]
c2 = list(c2)
if c1 == c2:
  print("YES")
else:
  print("NO")
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.append(0)
cost = 0
for i in range(N+1):
    cost += abs(A[i+1]-A[i])
for i in range(1,N+1):
    if A[i-1] <= A[i] <= A[i+1] or A[i+1] <= A[i] <= A[i-1]:
        sub = 0
    elif A[i-1] < A[i+1] < A[i]:
        sub = 2*(A[i]-A[i+1])
    elif A[i] < A[i-1] < A[i+1]:
        sub = 2*(A[i-1]-A[i])
    elif A[i+1] < A[i-1] < A[i]:
        sub = 2*(A[i] -A[i-1])
    elif A[i] < A[i+1]< A[i-1]:
        sub = 2*(A[i+1]-A[i])
    print(cost - sub)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.append(0)
cost = 0
for i in range(N+1):
    cost += abs(A[i+1]-A[i])
for i in range(1,N+1):
    sub = abs(A[i] - A[i+1]) + abs(A[i] - A[i-1]) - abs(A[i+1] - A[i-1])
    print(cost - sub)
import itertools
import numpy as np

def calc(n, a, b):
    if a > b:
        return 0
    elif a == b:
        return 1
    elif n == 1:
        return 0

    s = set()
    ary = np.arange(a, b+1)
    it = itertools.combinations_with_replacement(ary, n-2)
    for x in it:
        s.add(sum(x))

    return len(s)

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


print(calc(N, A, B))

### FIXED CODE ###


import itertools
import numpy as np

def calc(n, a, b):
    if a > b:
        return 0
    elif a == b:
        return 1
    elif n == 1:
        return 0

    return (b - a) * (n - 2) + 1

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


print(calc(N, A, B))
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        def k(s):
            if dp[s|c] > dp[s] + a
                dp[s|c] = dp[s] + a
        [k(s) for s in range(p)]
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

n, m = map(int, input().split())
ac = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    ac.append([a, c])
dp = [float('inf')] * 2**n
dp[0] = 0
for s in range(2**n):
    for a, c in ac:
        t = s|c
        if dp[t] > dp[s] + a:
            dp[t] = dp[s] + a
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)
N=int(input())
h=list(map(int,input().split()))
dp=[0,abs(h[1]-h[0])]
for i in range(2,N):
    dp.append(min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1])))
print(dp[i])

### FIXED CODE ###

N=int(input())
h=list(map(int,input().split()))
dp=[0,abs(h[1]-h[0])]
for i in range(2,N):
    dp.append(min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1])))
print(dp[-1])
input=sys.stdin.readline

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

### FIXED CODE ###

import sys

b = input()
if b == 'A':
	print('T')
elif b == 'T':
	print('A')
elif b == 'G':
	print('C')
elif b == 'C':
	print('G')
S= input()
if S==3 or S==5 or S==7:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

S=int(input())
if (S==3) or (S==5) or (S==7):
  print("YES")
else:
  print("NO")
n, m = map(int, input().split())
aL = [int(input()) for _ in range(m)]
mod = 10**9+7
cant = 0
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if aL[0] == 1 else 1
if dp[1] == 0:
    pos = 1
else:
    pos = 0
for i in range(n-1):
    if pos < len(aL):
        if i+2 == aL[pos]:
            if dp[i+1] > 0:
                dp[i+2] = 0
                pos += 1
            else:
                cant = 1
                break
        else:
            dp[i+2] += (dp[i] + dp[i+1]) % mod
    else:
        dp[i+2] += (dp[i] + dp[i+1]) % mod
if cant == 1:
    print(0)
else:
    print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
a_pos = [0]*(n+1)
for i in range(m):
    a_pos[int(input())] = 1
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if a_pos[1] else 1
for i in range(2, n+1):
    if a_pos[i] == 1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % mod

print(dp[-1])
N = int(input())
S = [c  for c in input()]

count = 0

for i in range(N):
  if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C" and i+2 <= N:
    count += 1

print(count)

### FIXED CODE ###

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

print(S.count("ABC"))
s = input()
t = input()

sl = len(s)
tl = len(t)
dp = [["" for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

for i in range(1,sl+1):
    for j in range(1,tl+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i-1][j]) > len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
display(dp[sl][tl])
    

### FIXED CODE ###

s = input()
t = input()

sl = len(s)
tl = len(t)
dp = [[0 for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

for i in range(1,sl+1):
    for j in range(1,tl+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

ansl = dp[sl][tl]
i = sl
j = tl
ans = [""]*ansl
while(ansl>0):
    if s[i-1] == t[j-1]:
        ans[ansl-1] = s[i-1]
        i -= 1
        j -= 1
        ansl -= 1
    elif dp[i][j]==dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print("".join(ans))
import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

ok = 0
for patterns in itertools.product((0, 1), repeat=M):
    patterns = list(patterns)
    is_lighting = True
    for i, lights in enumerate(connected_switches):
        turned_sw = sum([patterns[x] for x in lights])
        if turned_sw % 2 != conditions[i]:
            is_lighting = False
            break
    if is_lighting:
        ok += 1

print(ok)


### FIXED CODE ###

import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

ok = 0
for patterns in itertools.product((0, 1), repeat=N):
    patterns = list(patterns)
    is_lighting = True
    for i, lights in enumerate(connected_switches):
        turned_sw = sum([patterns[x] for x in lights])
        if turned_sw % 2 != conditions[i]:
            is_lighting = False
            break
    if is_lighting:
        ok += 1

print(ok)
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = map(int, input().split())

def binarySearch(array, target):
    l = len(array)
    first_half = array[:l//2]
    second_half = array[l//2:]
    if first_half == []:
        return False
    if first_half[-1] == target:
        return True
    elif first_half[-1] < target:
        return binarySearch(second_half, target)
    else:
        return binarySearch(first_half, target)

a = 0
for t in T: a += binarySearch(S, t)
print(a)

### FIXED CODE ###

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]

def f(P):
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= P:
            s += w[i]
            i += 1
            if i == n: return n
    return i

left = 0
right = 100000 * 10000

while right - left > 1:
    mid = (left + right) // 2
    v = f(mid)
    if v>=n:right=mid
    else: left = mid
print (right)
from collections import defaultdict
import math

def soi(num_ref):
    arr = []
    num = num_ref
    for i in range(2, int(math.sqrt(num))+1):
        if num%i == 0:
            cnt = 0
            while num%i == 0:
                cnt += 1
                num //= i
            arr.append([i, cnt])
    if num != 1:
        arr.append({num, 1})
    if arr == []:
        arr.append([num_ref, 1])
    return arr

N = int(input())
if N == 1:
    print(0)
    exit()
arr = soi(N)
cnt = 0
for i in arr:
    minus = 1
    tmp = i[1]
    while(tmp - minus >= 0):
        tmp -= minus
        minus += 1
        cnt += 1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
import math

def soi(num_ref):
    arr = []
    num = num_ref
    for i in range(2, int(math.sqrt(num))+1):
        if num%i == 0:
            cnt = 0
            while num%i == 0:
                cnt += 1
                num //= i
            arr.append([i, cnt])
    if num != 1:
        arr.append([num, 1])
    if arr == []:
        arr.append([num_ref, 1])
    return arr

N = int(input())
if N == 1:
    print(0)
    exit()
arr = soi(N)
cnt = 0
for i in arr:
    minus = 1
    tmp = i[1]
    while(tmp - minus >= 0):
        tmp -= minus
        minus += 1
        cnt += 1
print(cnt)