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

import sys
input = sys.stdin.readline
from heapq import *
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1<<100
    NN = T + 1
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    h = [0] * NN
    res = 0
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        q = []
        heappush(q, (0, s))
        while q:
            di, v = q.pop()
            if dist[v] < di: continue
            for i, (b, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[b] > dist[v] + c + h[v] - h[b]:
                    dist[b] = dist[v] + c + h[v] - h[b]
                    prevv[b] = v
                    preve[b] = i
                    heappush(q, (dist[b], b))
        
        
        if dist[t] == INF:
            return -1
        for v in range(NN):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * h[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
inf = 1 << 17
N, H, W = map(int, input().split())
S, T = H+W+N, H+W+N+1
for i in range(H):
    E.append((S, i, 1, 0))
for i in range(W):
    E.append((S, H+i, 1, 0))
for i in range(N):
    r, c, a = map(int, input().split())
    r -= 1
    c -= 1
    E.append((r, H+W+i, 1, 0))
    E.append((H+c, H+W+i, 1, 0))
    E.append((H+W+i, T, 1, inf - a))

E.append((S, T, H+W, inf))
print(inf * (H+W) - min_cost_flow_dijkstra(E, S, T, H+W))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    C[par(a)], C[par(b)] = C[par(a)] + C[par(b)], C[par(a)] + C[par(b)]
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)
N, H, W = map(int, input().split())
P = [-1 for i in range(H+W)]
C = [1] * (H+W)
X = []
for _ in range(N):
    r, c, a = map(int, input().split())
    X.append((a, r-1, c+H-1))
X = sorted(X)
ans = 0
while X:
    a, r, c = X.pop()
    unite(r, c)
    if C[par(r)]:
        ans += a
        C[par(r)] -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1

while n>1:
    ans *= n
    n -= 1
ans %= 10**9 + 7
print(ans)

### FIXED CODE ###

n = int(input())
ans = 1

while n>1:
    ans =  ans * n % (10**9 + 7)
    n -= 1
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
divider = 2019
min = divider
if (R - L >= 2018):
  min = 0
else:
  L = L % divider
  R = R % divider
if (L > R):
  min = 0
else:
  for i in range(L, R):
    # modulo = (i * i) % divider
    for j in range(i + 1, R + 1):
      # modulo = (modulo + i) % divider
      modulo = i * j % divider
      if (modulo < min):
        min = modulo
print(min)

### FIXED CODE ###

lr = input().split()
l = int(lr[0])
r = int(lr[1])
 
mini = 2018
 
for i in range(l, r+1):
  for j in range(i+1, r+1):
    mini = min(mini, (i*j)%2019)
 
    if mini==0:
      break
  if mini==0:
    break
print(mini)
### BUGGY CODE ###

# C - Welcome to AtCoder
# https://atcoder.jp/contests/abc151/tasks/abc151_c

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

# 問題数分配列を作成 -> 正解判定用の関数
tmp=[0]*m
ac = 0
wa = 0

tmp_wa = 0

for i in range(m):
    if ps[i][1] == "AC":
        # 正解したことのある問題か確認
        if ps[i][0] not in list(set(tmp)):
            ac += 1          
            wa = tmp_wa
            # tmp_wa = 0
            tmp[i] = ps[i][0]


    else:
        if ps[i][0] not in tmp:
            tmp_wa += 1


print(ac,wa)


# ACのカウントを数える
# ACが出るまでにでたWAをカウントする

# すでに正解済みの問題であれば、ACはカウントアップしない。

# すでに正解済みの問題であれば、ACはカウントアップしない。

# おそらく辞書を使う




### FIXED CODE ###

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

ac = [False] * N
wa = [0] * N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == 'AC':
        ac[p] = True
    else:
        if not ac[p]:
            wa[p] += 1

a = 0
b = 0
for i in range(N):
    if ac[i]:
        a += 1
        b += wa[i]
print(*[a, b])
### BUGGY CODE ###

#部分点解法
def inpl(): return input().split()
n, a = map(int, inpl())
x = list(map(int, inpl()))
x_minus_a = list(map(lambda x: x - a, x))

cnt = 0
for i in range(1, 2 ** n):
    s = 0
    for j in range(n):
        if (2 ** j) & i != 0:
           s += x_minus_a[j] 
    if s == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

def na(): return map(int, input().split())
n, a = na()
x = list(na())
xa = list(map(lambda f: f-a, x))
'''
dp[i][点数] = パターン数
i番目まで使用したときの点数になるパターン数
'''
dp = [dict() for _ in range(n)]
if xa[0] == 0:
    dp[0][0] = 2
else:
    dp[0][0] = 1
    dp[0][xa[0]] = 1
for i in range(1, n):
    #xa[i]を採用する / 採用しないで2つに分岐
    #すべて採用しないと点数0になるので、最後に点数0になったパターン数から1引く
    for k, v in dp[i-1].items():#k:得点, v:パターン数
        score = xa[i] + k
        dp[i][score] = dp[i].get(score, 0) + v#xa[i]を採用
        dp[i][k] = dp[i].get(k, 0) + v#xa[i]を不採用
print(dp[n-1][0] - 1)
### BUGGY CODE ###

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

word = input()

for _ in range(q):
    start, end = map(int, input().split())
    cnt = word[start-1:end].count('AC')
    print(cnt)


### FIXED CODE ###

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

word = input()

counter = [0] * n

for i in range(1, len(word)):
    counter[i] = counter[i-1]
    if word[i-1] + word[i] == 'AC':
        counter[i] += 1

for i in range(q):
    start, end = map(int, input().split())
    print(counter[end-1] - counter[start-1])
### BUGGY CODE ###

import numpy as np
N,K=map(int,input().split())
a = np.array([int(x) for x in input().split()])
v = np.array([1]*K)
print(max(np.convolve(a, v, mode='valid'))/2+0.5*K)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
a = np.array([int(x) for x in input().split()])
val=sum(a[:K])
max_val=val
for i in range(N-K):
  val+=a[K+i]
  val-=a[i]
  max_val=max(val,max_val)
print(max_val/2+K*0.5)
### BUGGY CODE ###

#ALDS1_4-B BinarySearch
c=0
n=input()
S = input().split()
q=input()
T = input().split()
for t in T:
    if( t in set(S)):c+=1
print(c)

### FIXED CODE ###

#ALDS1_4-B BinarySearch
input()
S=input().split()
input()
T=input().split()
print(len(set(S)&set(T)))
### BUGGY CODE ###

from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    elif s[i]=="B":
        b.append(i)
    else:
        pass
# print(r,g,b)

def mycount(r,g,b):
    c = 0
    for i in r:
        ng = [ x for x in g if x>i ]
        nb = [ x for x in b if x>i ]
        for j in ng:
            nb2 = [ y for y in b if y>j ]
            for k in nb2:
                if (j-i)!=(k-j):
                    c += 1
                else:
                    pass
        for j in nb:
            ng2 = [ y for y in g if y>j ]
            for k in ng2:
                if (j-i)!=(k-j):
                    c += 1
                else:
                    pass
    return c

ans = 0
ans += mycount(r,g,b)
ans += mycount(g,r,b)
ans += mycount(b,r,g)
print(ans)

### FIXED CODE ###

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    elif s[i]=="B":
        b.append(i)
    else:
        pass
# print(r,g,b)
count = 0
for i in range(n):
    x = s[i]
    for sa in range(n):
        j = i + sa
        k = j + sa
        if j<n:
            y = s[j]
        else:
            break
        if k<n:
            z = s[k]
        else:
            break
        if x!=y and y!=z and z!=x:
            count += 1
# print(count)
ans = len(r) * len(g) * len(b) - count
print(ans)
### BUGGY CODE ###

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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf') for _ in range(H + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])

### FIXED CODE ###

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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])
### BUGGY CODE ###

s = list(map(ord, input()))
K = int(input())

asca = 97
ascz = 122
start = 0
lens = len(s)

loop = lambda x: asca if x == ascz else x+1

for k in range(K):
    for i in range(start, lens):
        c = s[i]
        if i == lens - 1:
            s[i] = loop(c)
            break
        if c == asca:
            start += 1
            continue
        v = c + (K-k)
        if v > ascz:
            s[i] = loop(c)
            break
        else:
            continue
print(''.join(map(chr, s)))


### FIXED CODE ###

s = list(map(ord, input()))
K = int(input())

asca = 97
ascz = 122
start = 0
lens = len(s)

loop = lambda x: asca if x == ascz else x+1

for k in range(K):
    if start == lens - 1:
        for i in range((K-k) % (ascz - asca + 1)):
            s[start] = loop(s[start])
        break
    for i in range(start, lens):
        c = s[i]
        if i == lens - 1:
            s[i] = loop(c)
            break
        if c == asca:
            start += 1
            continue
        v = c + (K-k)
        if v > ascz:
            s[i] = loop(c)
            break
        else:
            continue
print(''.join(map(chr, s)))
### BUGGY CODE ###

import numpy as np

d = int(input())
C = np.array(list(map(int, input().strip().split())))
S = np.array([list(map(int, input().strip().split())) for i in range(d)])

D = np.zeros(26)
s_d = np.zeros(d)
W = np.ones(26) + C / 100
out = np.zeros(d)
t = 0
for k in range(100):
    for i in range(d):
        day = i + 1
        temp_score = 0
        con = 0
        d_l = [day]*26
        for j in range(26):
            score = S[i][j]
            score -= sum((d_l - D) * C)
            score += (day - D[j]) * C[j] * W[j]
            if score > temp_score:
                con = j
                temp_score = score
        out[i] = con + 1
        D[con] = i + 1
        t += temp_score
        s_d[i] = t
        W = W * 0.95
        W[j] = W[j] * 1.05
for i in out:
    print(int(i))


### FIXED CODE ###

import numpy as np

d = int(input())
C = np.array(list(map(int, input().strip().split())))
S = np.array([list(map(int, input().strip().split())) for i in range(d)])
D = np.zeros(26)

t = 0
for i in range(d):
    day = i + 1
    temp_score = 0
    con = 0
    d_l = [day]*26
    for j in range(26):
        score = S[i][j]
        score -= sum((d_l - D) * C)
        score += (day - D[j]) * C[j]
        if score > temp_score:
            con = j
            temp_score = score
    print(con + 1)
    D[con] = i + 1
    t += temp_score
### BUGGY CODE ###

N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            for k in range(1, i+1):
                tmp = max(dp[i-k][j], dp[i-k][j-w] + v)
                dp[i][j] = max(dp[i][j], tmp)

print(dp[-1][-1])


### FIXED CODE ###

N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
#S  = input()
s = []
for i in range(Q):
    l,r = map(int,input().split())
    s.append(0)
    for j in range(l-1,r-1):
        if S[j] is "A" and S[j+1] is "C":
            s[i] += 1
for i in range(Q):
    print(s[i])
#for i in range(Q):
#    print(S[i].count("AC"))

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
a =[0] * N
for i in range(N-1):
    if S[i] == "A" and S[i + 1] == "C":
        a[i + 1] = a[i] + 1
    else:
        a[i + 1] = a[i]
l, r = 0, 0
b = [0] * Q
for i in range(Q):
    l, r = map(int, input().split())
    b[i] = a[r-1] - a[l-1]
for i in range(Q):
    print(b[i])
### BUGGY CODE ###

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

ch = 1
ind = 0
bits = [ch]
while ch*2 <= K:
    ind += 1
    ch *= 2
    bits.append(ch)

#print(ch,ind)
#ch_max = 2**(ind+1) -1
#print(ch_max)

tmp = [0 for _ in range(ind+1)]

for a in A:
    for i,bit in enumerate(bits):
        if a & bit:
            tmp[i] = tmp[i] + 1
#print(tmp)

ans_x = 0
for i,t in enumerate(tmp):
    if 2*t < N and K > 0:# and ans_x + bits[i] <= K:
        ans_x += bits[i]
#        print('koko')
    else:
        ans_x += 0
#        print(bits[i])

ans = 0
if ans_x <= K:
    for n in range(N):
        ans += ans_x ^ A[n]
else:
    ans_max = 0
    for i in range(10000):
        ans_tmp = 0
        for n in range(N):
            ans_tmp += (K-i) ^ A[n]
        ans_max = max(ans_tmp,ans_max)

    ans = ams_max

    # for i in range(ans_x - bits[-1],K+1):
    #     ans_x2 = i
    #     ans_tmp = 0
    #     for n in range(N):
    #         ans_tmp += ans_x2 ^ A[n]
    #     ans_max = max(ans_max, ans_tmp)

    # ans = ans_max

print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/abc117/submissions/4165407
n,k=map(int,input().split())
a=list(map(int,input().split()))
t,ans=2**40,0
while t:
    c=sum([(a[i]&t)//t for i in range(n)])
    if k<t or c*2>=n:
        ans+=t*c
    else:
        ans+=t*(n-c)
        k -= t
    t //= 2

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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

N = I()
A = III()
B = III()

x = []
for i in range(N):
    heapq.heappush(x,(-B[i],i))

counter = 0

while x:
    temp = heapq.heappop(x)
    i = temp[1]
    b = -temp[0]
    a = B[(i-1)%N]
    c = B[(i+1)%N]
    if b == A[i]:
        continue
    elif b<A[i]:
        print(-1)
        exit()
    else:
        d,m = divmod(b-A[i],a+c)
        if d==0:
            print(-1)
            exit()
        elif m == 0:
            B[i] = A[i]
            counter += d
        else:
            B[i] = A[i]+m
            heapq.heappush(x,(-B[i],i))
            counter += d

print(counter)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

N = I()
A = III()
B = III()

x = []
for i,b in enumerate(B):
    heapq.heappush(x,(-b,i))

counter = 0

while x:
    temp = heapq.heappop(x)
    i = temp[1]
    b = -temp[0]
    a = B[(i-1)%N]
    c = B[(i+1)%N]
    if b == A[i]:
        continue
    elif b<A[i]:
        print(-1)
        exit()
    else:
        d,m = divmod(b-A[i],a+c)
        if d==0:
            print(-1)
            exit()
        elif m == 0:
            B[i] = A[i]
            counter = counter+d
        else:
            B[i] = A[i]+m
            heapq.heappush(x,(-B[i],i))
            counter = counter+d

print(counter)
### BUGGY CODE ###

a=input()
num=len(a)
mod_map={0:1}
mod_list=[1]+[0]*2019
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    mod_list[mod]+=1

res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)

### FIXED CODE ###

a=reversed(input())
#num=len(a)
mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    mod_list[mod]+=1
res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)
### BUGGY CODE ###

from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

max_num = 0
for i in range(H):
    for j in range(W):
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] in hw:
                max_num = max(max_num, max_A + max_B - 1)
            else:
                max_num = max(max_num, max_A + max_B)

print(max_num)


### FIXED CODE ###

H, W, M = map(int, input().split())
hw = set()
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.add((h, w))
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if (i + 1, j + 1) not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int, input().split()))
temp_1 = 1 #今
temp_2 = 1 #昔

for i in range(N):
    if i==0:
        temp_1 *= A[i]
    elif i<=(K-1):
        temp_2 = temp_1
        temp_1 *= A[i]
    if i>(K-1):
        temp_2 = temp_1
        temp_1 /= A[i-K]
        temp_1 *= A[i]
        if temp_2<temp_1:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int, input().split()))
temp_1 = 1 #今
temp_2 = 1 #昔

for i in range(N):
    if i>(K-1):
        if A[i-K]<A[i]:
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

def factorint(N):
    """
    Nを作っている素数を辞書で返す．
    input 100
    output Counter({2: 2, 5: 2})
    """
    table = []
    tmp = 2
    while(N > 1):
        for i in range(tmp,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    table.append(i)
                tmp = i+1
                break
    table_ = collections.Counter(table)
    return table_

factors = factorint(N)
ans = 0

for key in factors.keys():
    f_c = factors[key]
    tmp = 1
    while f_c >= tmp:
        ans += 1
        f_c -= tmp
        tmp += 1

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

def factorint(N):
    """
    Nを作っている素数を辞書で返す．
    input 100
    output Counter({2: 2, 5: 2})
    """
    table = []
    tmp = 2
    while(N > 1):
        for i in range(tmp,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    table.append(i)
                tmp = i+1
                break
    table_ = collections.Counter(table)
    return table_

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt

# factors = factorint(N)
factors = primes(N)
ans = 0

for key in factors.keys():
    f_c = factors[key]
    tmp = 1
    while f_c >= tmp:
        ans += 1
        f_c -= tmp
        tmp += 1

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

S = input()
lenS = len(S)
index = 0
ans = lenS
while index < lenS-1:
    if S[index:index+2] == "ST":
        S = S[:index] + S[index+2:]
        ans -= 2
        index -= 1
    else:
        index += 1
print(str(ans))

### FIXED CODE ###

from collections import deque

S = input()
lenS = len(S)
pops = 0
ans = lenS
stack = deque()
for i in range(lenS):
    if stack and S[i] == "T":
        a = stack.pop()
        if a == "S":
            ans -= 2
    else:
        stack.append(S[i])
print(str(ans))