Harryxun/stf_run huggingface dataset:
from functools import lru_cache

L = input().split()
sprime = 998244353 # approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

@lru_cache(maxsize=N)
def factorial(m):
	a = 1
	for i in range(1,m):
		a = (a*i) % sprime

def binom(m):
	if N == m:
		return 1
	elif m == 1:
		return N
	elif m > N:
		return 0
	else:
		return (a * modinv(b,sprime) * modinv(c*sprime)) % sprime

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 
# max is A*N + B*N
sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime

print(sum)
import sys
import math
r = int(sys.stdin.readline())

print "%.6f, %.6f"%(math.pi*r*r, 2*math.pi*r)

### FIXED CODE ###

import sys
import math
r = float(sys.stdin.readline())
  
print "%.6f %.6f"%(math.pi*r*r, 2*math.pi*r)
# C - Welcome to AtCoder
# https://atcoder.jp/contests/abc151/tasks/abc151_c

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

ac = 0
wa = 0

AC = "AC"
WA = "WA"

tmp_wa = 0
tmp_ac = 0


for i in range(len(submits)):
    # ACなら正解数をカウントアップ
    if submits[i][1] == AC:
        # 同じ問題に正解してないかチェック
        if submits[i][0] == tmp_ac:
            continue
        ac += 1
        # WAの数をカウント
        wa += tmp_wa
        # WAを初期化
        tmp_wa = 0
        tmp_ac = submits[i][0]
    else:
        # WAならwa+1
        tmp_wa += 1

print(ac + " " + wa)

### 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])
import sys
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())
xyz = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append(y)
    xyz[y].append(x)
    
ans = 0
visited = [False]*(n+1)
def dfs(x):
    visited[x] = True
    for y in xyz[x]:
        if not visited[y]:
            dfs(y)

for x in range(1, n+1):
    if visited[x]:
        continue
    dfs(x)
    ans += 1
    
# print(visited)
print(ans)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
xyz = {i:[] for i in range(1, n+1)}
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append((x, y, z))
    xyz[y].append((y, x, z))

connects = [0]*(n+1)
group = 1
for i in range(1, n+1):
    if connects[i] > 0:
        continue
    if len(xyz[i]) == 0:
        connects[i] = group
        group += 1
        continue

    que = deque(xyz[i])
    connects[i] = group
    while len(que) > 0:
        x, y, z = que.popleft()
        connects[y] = group
        for xn, yn, zn in xyz[y]:
            if connects[yn] > 0:
                pass
            else:
                que.append((xn, yn, zn))
    group += 1
    
# print(connects)
print(max(connects))
A,B,C,D,E,F=map(int,input().split())
E=E/(100+E)
M=[]
S=[]
for i in range(F//100*A+1):
    for j in range(F//100*B+1):
        t=i*100*A+j*100*B
        if t<=F and t!=0:
            M.append(t)
for i in range(F//C+1):
    for j in range(F//D+1):
        ta=i*C+j*D
        if ta<=F:
            S.append(ta)
tmp=0
for x in M:
    for y in S:
        f=x+y
        e=(100*y)/f
        if f<=F and e<=E:
            if e>tmp:
                tmp=e
                ans1,ans2=f,y
print(ans1,ans2)

### FIXED CODE ###

a,b,c,d,e,f=map(int,input().split())
a=100*a
b=100*b
dp1=[0]*(f+1)
dp2=[0]*(f+1)
for i in range(f+1):
    if i%a==0:
        if i+a<=f:
            dp1[i+a]=1
for i in range(f+1):
    if i==0 or dp1[i]==1:
        if i+b<=f:
            dp1[i+b]=1
for i in range(f+1):
    if i%c==0:
        if i+c<=f:
            dp2[i+c]=1
for i in range(f+1):
    if i==0 or dp2[i]==1:
        if i+d<=f:
            dp2[i+d]=1

ans=[-1,-1,-1]
for i in range(f+1):
    if dp1[i]==1:
        x=min(f-i,(i//100)*e)
        k=-1
        for j in range(x,-1,-1):
            if dp2[j]==1 or j==0:
                k=j
                if ans[0]<100*k/(i+k):
                    ans=[100*k/(i+k),i+k,k]
                break
print(str(ans[1])+" "+str(ans[2]))
n, m, k = map(int, input().split())

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

time = 0
count = 0
for _ in range(n + m):
    if len(a) > 0 and len(b)>0:
        if a[0] < b[0]:
            time += a[0]
            a = a[1:]
        else:
            time += b[0]
            b = b[1:]
    elif len(a) == 0 and len(b) > 0:
        time += b[0]
        b = b[]
    elif len(b) == 0 and len(a) > 0:
        time += a[0]
        a = a[:-1]
    if time > k:
        break
    else:
        count += 1
        
        
print(count)

### FIXED CODE ###

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

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

a, b = [0], [0]
for  i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i] + B[i])

ans, j = 0, m
for i in range(n+1):
    if a[i]>k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
def workC():
    
    x,n = map(int,input().split())
    l = list(map(int,input().split()))

    if n == 0:
        return x
    
    if n == 100:
        return 0
    
    for i in range(x,maxx):
        if not i in l:
            u = i
            #dic.setdefault(i,abs(i-x))
            break
    
    for i in range(x,minx,-1):
        if not i in l:
            d = i
            #dic.setdefault(i,abs(x-i))
            break
    
    if abs(x-u) == abs(x-d):
        return min(u,d)
    elif abs(x-u) < abs(x-d):
        return u
    else:
        return d

u=999
d=999
minx = 1-1
maxx = 100+1

ans = workC()
print(ans)

### FIXED CODE ###

import sys

X, N = map(int,input().split())
p = list(map(int,input().split()))

for d in range(X + 1):
    for s in [-1, +1]:
        a = X + s * d
        if p.count(a) == 0:
            print(a)
            sys.exit(0)
if '7' in str(N):
	print ('Yes')
else:
  	print ('No')

### FIXED CODE ###

N=input()
if '7' in N:
  print('Yes')
else:
  print('No')
#input an interget
K=int(input())
#input an string
S=str(input())
#get the length of the string
x=int(len(str1))
#get the difference in length between k and s
i=x-k

#make a second string for the appending
S2="..."

#if statement about how the string will function
#if the string is the same length as k then print it
if i==0:
    print(S)
#if not, delete the last character of the string
else:
    for i in range(x):
        S=S[i]
#and then join the two strings together
    newstr="".join((S,S2))
    print(newstr)


### FIXED CODE ###

# Take the input K
# Take the inpus S

#Compare the length of S with K and put in in length
#If length<=K... print all
#If length>K... print some of the character

K = int(input()) # 0(1)
S = input() #0(1)
second_answer = [] #0(1)
x = 0 #0(1)

length = len(S) #0(1)

if length <= K : 
    print(S) #0(1)
else:
    while x<K : #0(K)
        print(S[x], end= (""))
        x += 1
    print("...")
n = int(input())
a = list(map(int, input().split()))

ans = []

for i in range(n):
    s = a[i]
    ans[s-1] = i + 1
    
print(ans)

### FIXED CODE ###

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

ans = [0] * n

for i in range(n):
    s = a[i]
    ans[s-1] = i + 1

print(*ans)
import math
a,b = map(float, input().split())
print(math.floor((a*(b*100)/100))

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int("".join(b.split(".")))
print((a*b)//100)
class DisjoinSet:
    def __init__(self, size):
        self.rank = [0 for _ in range(size)]
        self.p = [0 for _ in range(size)]
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = x

    def same(self, x, y):
        print(int(self.findSet(x) == self.findSet(y)))

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # ???????±???????
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


if __name__ == '__main__':
    n, q = map(int, input().split())
    D = DisjoinSet(n)
    cmd = {0: lambda x, y: D.unite(x, y), 1: lambda x, y: D.same(x, y)}
    for _ in range(q):
        c, x, y = map(int, input().split())
        cmd[c](x, y)

### FIXED CODE ###

class DisjoinSet:
    def __init__(self, size):
        self.rank = [0 for _ in range(size)]
        self.p = [0 for _ in range(size)]
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def same(self, x, y):
        print(int(self.findSet(x) == self.findSet(y)))

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # ???????±???????
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


if __name__ == '__main__':
    n, q = map(int, input().split())
    D = DisjoinSet(n)
    cmd = {0: lambda x, y: D.unite(x, y), 1: lambda x, y: D.same(x, y)}
    for _ in range(q):
        c, x, y = map(int, input().split())
        cmd[c](x, y)
a = input()
a + a * 2 + a * 3 = Z
 print(Z)


### FIXED CODE ###

a = int(input())
print(a + a**2 + a**3)
a1=[map(int(),input().split())]
a2=[map(int(),input().split())]
a3=[map(int(),input().split())]
n=int(input())
b=[input() for i in range(n)]
for i in range(3):
    for j in range(N):
        if a1[i] == b[j]:
            a1[i] = 1
        elif a2[i] == b[j]:
            a2[i] = 1
        elif a3[i] == b[j]:
            a3[i] = 1
 
print(line1)
print(line2)
print(line3)

if a1[0] == a1[1] == a1[2]:
    print("Yes")
elif a2[0] == a2[1] == a2[2]:
    print("Yes")
elif a3[0] == a3[1] == a3[2]:
    print("Yes")
elif a1[0] == a2[0] == a3[0]:
    print("Yes")
elif a1[1] == a2[1] == a3[1]:
    print("Yes")
elif a1[2] == a2[2] == a3[2]:
    print("Yes")
elif a1[0] == a2[1] == a3[2]:
    print("Yes")
elif a1[2] == a2[1] == a3[0]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a1=list(map(int,input().split()))
a2=list(map(int,input().split()))
a3=list(map(int,input().split()))
n=int(input())
b=[int(input()) for i in range(n)]
for i in range(3):
    for j in range(n):
        if a1[i] == b[j]:
            a1[i] = 1
        elif a2[i] == b[j]:
            a2[i] = 1
        elif a3[i] == b[j]:
            a3[i] = 1
 
if a1[0] == a1[1] == a1[2]:
    print("Yes")
elif a2[0] == a2[1] == a2[2]:
    print("Yes")
elif a3[0] == a3[1] == a3[2]:
    print("Yes")
elif a1[0] == a2[0] == a3[0]:
    print("Yes")
elif a1[1] == a2[1] == a3[1]:
    print("Yes")
elif a1[2] == a2[2] == a3[2]:
    print("Yes")
elif a1[0] == a2[1] == a3[2]:
    print("Yes")
elif a1[2] == a2[1] == a3[0]:
    print("Yes")
else:
    print("No")
n=int(input())
a_list=list(map(int,input().split()))
cnt = [0] * int(1e5 + 10)
sum=0
for i in a_list:
 cnt[i] +=1
 sum+=i
q=int(input())
ans=0
 
for j in range(q):
 x,y=map(int,input().split())
 sum+=(x-y)*cnt[x]
 print(sum)
 cnt[x]+=cnt[y]

### FIXED CODE ###

import re
a=input()
if re.sub(r'[A-Z]',"",a)=="":
  print('A')
else:
  print('a')
n, l = map(int, input().split())
S = [int(input()) for i in range(n)]
sorted_list = sorted(S)
print(*sorted_list, sep="")

### FIXED CODE ###

n, l = map(int, input().split())
S = [input() for i in range(n)]
sorted_list = sorted(S)
print(*sorted_list, sep="")
n = str(input())
sum = 0
for i in range(0, len(str(input()))): sum += int(n[i])
if int(n) % sum == 0: print("Yes")
else: print("No")

### FIXED CODE ###

n = str(input())
sum = 0
for i in range(0, len(n)):
  sum += int(n[i])
n = int(n)
if n % sum == 0:
  print("Yes")
else:
  print("No")
a,b = map(int, input().split())
if a >= 13:
    print(b)
elif 5 <= a <= 12:
    print(int(b/2))
else:
    print(0

### FIXED CODE ###

a,b = map(int, input().split())
if a >= 13:
    print(b)
elif a >= 6 and a <= 12:
    print(b//2)
else:
    print(0)
s=input()
a=753
for i in range(len(s)-2):
  a=min(a, abs(753-int(s[i:i+3])))
print(a)

s=input()
like=753
ans=753
for i in range(len(s)-2):
    ans=min(ans,abs(like-int(s[i:i+3])))
print(ans)

### FIXED CODE ###

s=input()
a=753
for i in range(len(s)-2):
  a=min(a, abs(753-int(s[i:i+3])))
print(a)
a = int(input())
b = int(input())
if a > b:
   print("a > b")
elif a < b:
   print("a < b")
else:
   print("a == b")

### FIXED CODE ###

a,b = map(int,input().split()) 
if a > b:
   print("a > b")
elif a < b:
   print("a < b")
else:
   print("a == b")
import sys
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
box,box2 = [],[]
acnt = dict(Counter(a))
acnt = sorted(acnt.items(), key=lambda x:x[0],reverse=True)
a_val = [acnt[x][1] for x in range(len(acnt))]
a_key = [acnt[y][0] for y in range(len(acnt))]
for i in range(len(a_val)):
	if a_val[i] >= 4:
		box2.append(a_key[i]**2)
	if 2 <= a_val[i]:
		box.append(a_key[i])
box.sort(reverse=True)
if len(box2) >= 2:	
	ans = max(box2)
if len(box) >= 2:
    print(max(ans,(box[0]*box[1])))
    sys.exit()
print(0)


### FIXED CODE ###

import sys
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
box,box2,ans = [],[],0
acnt = dict(Counter(a))
acnt = sorted(acnt.items(), key=lambda x:x[0],reverse=True)
a_val = [acnt[x][1] for x in range(len(acnt))]
a_key = [acnt[y][0] for y in range(len(acnt))]
for i in range(len(a_val)):
	if a_val[i] >= 4:
		box2.append(a_key[i]**2)
	if 2 <= a_val[i]:
		box.append(a_key[i])
box.sort(reverse=True)
if len(box2) >= 2:	
	ans = max(box2)
if len(box) >= 2:
    print(max(ans,(box[0]*box[1])))
    sys.exit()
print(0)
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


abcd = input().split(" ")
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
cd = lcm(c, d)

print(b-a+1 - ((b+1)//c - a//c) - ((b+1)//d - a//d) + ((b+1)//cd - a//cd))


### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
abcd = input().split(" ")
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
cd = lcm(c, d)
print(b-a-(b//c-((a-1)//c + 1))-(b//d - ((a-1)//d + 1))+(b//cd-((a-1)//cd + 1)))
L,R=map(int,input().split())
list=[]
if (R-L)>=2018:
  print(0)
else:
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
print(ans)

### FIXED CODE ###

L,R=map(int,input().split())
if (R-L)>=2018:
  print(0)
else:
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
  print(ans)
N, u, v = list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
for i in range(N-1):
  A, B = list(map(int, input().split()))
  graph[A].append(B)
  graph[B].append(A)
#print(graph)

def dfs(v):
  dist = [-1] * (N+1)
  dist[v] = 0
  stack = [v
 # print(dist)
  while stack:
    now = stack.pop()
    dw = dist[now] + 1
#graph[]は隣接している要素
    for ne in graph[now]:
      if dist[ne] >= 0:
        continue
      dist[ne] = dw
      stack.append(ne)
      #print(ne)
  return dist

Taka = dfs(u)
#Ao = dfs(v)

print(Taka)
#print(Ao)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
  if t < a:
    ans = max(ans, a-1)

print(ans)

### FIXED CODE ###

import sys

n, u, v = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)
from collections import deque
from collections import Counter

h,w = map(int,input().split())

c = [None]*h
d = [[-1 for i in range(w)] for j in range(h)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
kk = 0

for i in range(h):
    c[i] = input()
    
for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            d[i][j] = 0
    
def bfs(y,x):
    global kk
    d[y][x] = -1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and d[ny][nx] != -1:
            kk += 1
            bfs(ny,nx)
            

resmin  = 100000
an = []
res = 0
for i in range(h):
    for j in range(w):   
        if d[i][j] == 0:
            bfs(i,j)
            res += 1
            an.append(kk+1)
            
b = Counter(an)
if b[1] != 0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

import sys

h,w = map(int,input().split())
c = [None]*h
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(h):
    c[i] = input()
    
for i in range(h):
    for j in range(w):
        a = 0
        b = 0
        for k in range(4):
            nx = j + dx[k]
            ny = i + dy[k]
            if c[i][j] == '#' and 0<=nx and nx<w and 0<=ny and ny<h:
                b += 1
                if c[ny][nx] == '.':
                    a += 1
                    
        if a == b and b != 0:
            print("No")
            sys.exit()
            
print("Yes")
S = list(input())
s1 = list("keyence")

x = [1]
y = [1]
for i in range(7):
  if S[i] == s1[i]:
    x.append(x[i])
  if S[len(S)-1-i] == s1[6-i]:
    y.append(y[i])
  

if sum(x) + sum(y) >= 9:
  print("YES")  
else:
  print("NO")

### FIXED CODE ###

S = list(input())
s1 = list("keyence")

x = []
y = []
for i in range(7):
  if S[i] == s1[i]:
    x.append(1)
  if S[len(S)-1-i] == s1[6-i]:
    y.append(1)
  

if sum(x) + sum(y) >= 7:
  print("YES")  
else:
  print("NO")
N, K = map(int, input().split())
P = list(map(lambda x:int(x) - 1, input().split()))
C = list(map(int, input().split()))

L = [[] for _ in range(N)]
for i in range(N):
    cnt = C[i]
    blk = P[i]
    L[i].append([cnt, blk])
    for j in range(N):
        li = L[i][j][1]
        if li == i:
            break
        else:
            cnt += C[li]
            blk = P[li]
            L[i].append([cnt, blk])

ans = []
for l in L:
    maxl = 0
    lenl = len(l)
    modK = K % lenl
    numK = K // lenl
    if l[lenl - 1][0] > 0:
        maxl += numK * l[lenl - 1][0]
        maxl += max(l[:modK], key = lambda x:x[0])[0]
    else:
        maxl += max(l[:min(K, lenl)], key = lambda x:x[0])[0]
    ans.append(maxl)

print(max(ans))
            

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(lambda x:int(x) - 1,input().split()))
C = list(map(int, input().split()))
ans = -10**9

for i in range(N):
    tmp_max = [-10**9]*(N+1)
    total = 0
    current_block = P[i]
    for j in range(1, N + 1):
        total += C[current_block]
        tmp_max[j] = max(tmp_max[j-1], total)
        if current_block == i:
            break
        current_block = P[current_block]
    if total <= 0:
        ans = max(ans, tmp_max[j])
    else:
        n = K // j
        r = K % j
        if r == 0:
            ans = max(ans, total*(n-1) + tmp_max[j])
        else:
            ans = max(ans, total*n + tmp_max[r])

print(ans)
sieve = [True] * 10**6
prime = []
for i in range(2, 10**6):
  if sieve[i]:
    prime.append(i)
    if i < 10**3:
      for j in range(i**2, 10**6, i):
        sieve[j] = False
n = int(input())
if n == 1:
  print(0)
else:
  e = []
  for p in prime:
    if n % p == 0:
      idx = 0
      while n % p == 0:
        n = n // p
        idx += 1
      e.append(idx)
    if n == 1:
        break
  if len(e) > 0:
    total = 0
    for idx in e:
      cnt = 1
      while idx => cnt*(cnt+1)//2:
        cnt += 1
      cnt -= 1
      total += cnt 
    if n == 1:
      print(total)
    else:
      print(total + 1)
  else:
    print(1)


### FIXED CODE ###

sieve = [True] * 10**6
prime = []
for i in range(2, 10**6):
  if sieve[i]:
    prime.append(i)
    if i < 10**3:
      for j in range(i**2, 10**6, i):
        sieve[j] = False
n = int(input())
if n == 1:
  print(0)
else:
  e = []
  for p in prime:
    if n % p == 0:
      idx = 0
      while n % p == 0:
        n = n // p
        idx += 1
      e.append(idx)
    if n == 1:
        break
  if len(e) > 0:
    total = 0
    for idx in e:
      cnt = 1
      while idx >= cnt*(cnt+1)//2:
        cnt += 1
      cnt -= 1
      total += cnt 
    if n == 1:
      print(total)
    else:
      print(total + 1)
  else:
    print(1)
n, m = map(int, input().split())
sus = [[] for i in range(n)]
eq = [1 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    sus[a - 1].append(b - 1)
    sus[b - 1].append(a - 1)

valid = [True for i in range(n)]

def dfs(x):
    ret = 1
    valid[x] = False
    for y in sus[x]:
        if valid[y]:
            valid[y] = False
            ret += dfs(y)
    return ret

color = [-1 for i in range(n)]
sol = 0
cnt = [0, 0]

def boji(x):
    global cnt
    cnt[color[x]] += 1
    for y in sus[x]:
        if color[y] == -1:
            color[y] = 1 - color[x]
            if boji(y):
                return True
        elif color[y] == color[x]:
            return True
    return 0

for i in range(n):
    if color[i] == -1 and valid[i]:
        cnt = [0, 0]
        color[i] = 0
        if boji(i) == 0:
            sol += cnt[0] * cnt[1]
        else:
            d = dfs(i)
            sol += d * (d - 1) // 2
print(sol - m)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5 + 1)

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

valid = [True for i in range(n)]

def dfs(x):
    ret = 1
    valid[x] = False
    for y in sus[x]:
        if valid[y]:
            valid[y] = False
            ret += dfs(y)
    return ret

color = [-1 for i in range(n)]
sol = 0
cnt = [0, 0]

def boji(x):
    global cnt
    cnt[color[x]] += 1
    for y in sus[x]:
        if color[y] == -1:
            color[y] = 1 - color[x]
            if boji(y):
                return True
        elif color[y] == color[x]:
            return True
    return 0

for i in range(n):
    if color[i] == -1 and valid[i]:
        cnt = [0, 0]
        color[i] = 0
        if boji(i) == 0:
            sol += cnt[0] * cnt[1]
        else:
            d = dfs(i)
            sol += d * (d - 1) // 2
print(sol - m)
o = input().strip()
e = input().strip()

a = ''

if len(o)-len(e) == 0:
    for i in range(len(o)):
        a += o[i]
        a += e[i]
    print(a)
else:
    for i in range(len(e)):
        a += o[i]
        a += e[i]
    a += o[len(o)]
    print(a)

### FIXED CODE ###

o = input().strip()
e = input().strip()

a = ''

if len(o)-len(e) == 0:
    for i in range(len(o)):
        a += o[i]
        a += e[i]
    print(a)
else:
    for i in range(len(e)):
        a += o[i]
        a += e[i]
    a += o[len(o)-1]
    print(a)