Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
ABs = []
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  ABs.append((A, B))
UF = list(range(N))
Ns = [1]*N
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[i] = j
  Ns[i] = Ns[j] = Ns[i]+Ns[j]
def size(m):
  return Ns[par(m)]
r = N*(N-1)//2
rs = [r]
for A, B in reversed(ABs):
  if par(A) == par(B):
    rs.append(r)
    continue
  sA = size(A)
  sB = size(B)
  unite(A, B)
  r -= sA*sB
  rs.append(r)
rs.pop()
for r in reversed(rs):
  print(r)


### FIXED CODE ###

N, M = map(int, input().split())
ABs = []
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  ABs.append((A, B))
UF = list(range(N))
Ns = [1]*N
def par(m):
  s = []
  r = UF[m]
  while r != m:
    s.append(m)
    m = r
    r = UF[m]
  for i in s:
    UF[i] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
  Ns[i] = Ns[j] = Ns[i]+Ns[j]
def size(m):
  return Ns[par(m)]
r = N*(N-1)//2
rs = [r]
for A, B in reversed(ABs):
  if par(A) == par(B):
    rs.append(r)
    continue
  sA = size(A)
  sB = size(B)
  unite(A, B)
  r -= sA*sB
  rs.append(r)
rs.pop()
for r in reversed(rs):
  print(r)
def INT():
    return int(input())

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

def LI():
    return list(map(int, input().split()))

N, P = MI()
g = 1
mod = 1
ans = 0

while mod <= P:
    mod = pow(g, N)
    
    if P % pow(g, N) == 0:
        ans = max(ans, g)
    
    g += 1
    mod = pow(g, N)
    
print(ans)

### FIXED CODE ###

def INT():
    return int(input())

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

def LI():
    return list(map(int, input().split()))

def factrize(P):
    fac = {}
    
    for i in range(2, int(P**0.5) + 1):
        e = 0
        while P % i == 0:
            P //= i
            e += 1
            
        if e > 0:
            fac[i] = e
    
    if P > 1:
        fac[P] = 1
    
    return fac

N, P = MI()
ans = 1

for f, e in factrize(P).items():
    if e >= N:
        ans *= f**(e // N)
        
print(ans)
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
#	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
#		search(values,hp+dh,vp+dv,item)
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		print(solve(list(list(input().strip()) for _ range(H))))
		line = input().strip()

if __name__=='__main__':
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), a))
heapq.heapify(a)
for _ in range(m):
    min = ((heapq.heappop(a) * (-1)) // 2) * (-1)
    heapq.heappush(a, min)
print(sum(a)*(-1))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x * (-1), a))
heapq.heapify(a)
for _ in range(m):
    min = ((heapq.heappop(a) * (-1)) // 2) * (-1)
    heapq.heappush(a, min)
print(sum(a)*(-1))
A,B = int(input())
print(A*B if A<= 9 and B <=9 else -1)

### FIXED CODE ###

A,B = map(int,input().split())
print(A*B if A<= 9 and B <=9 else "-1")
# -*- coding:utf-8 -*-
N = int(input())
a = list(map(int, input().split()))
rate = [ 0 for tmp in range(9) ]
factor = 0
empty = 0
for tmp in range(N):
    if 1 <= a[tmp] and  a[tmp] <= 399:
        rate[0] += 1
    elif 400 <= a[tmp] and a[tmp] <= 799:
        rate[1] += 1
    elif 800 <= a[tmp] and a[tmp] <= 1199:
        rate[2] += 1
    elif 1200 <= a[tmp] and a[tmp] <= 1599:
        rate[3] += 1
    elif 1600 <= a[tmp] and a[tmp] <= 1999:
        rate[4] += 1
    elif 2000 <= a[tmp] and a[tmp]<= 2399:
        rate[5] += 1
    elif 2400 <= a[tmp] and a[tmp] <= 2799:
        rate[6] += 1
    elif 2800 <= a[tmp] and a[tmp] <= 3199:
        rate[7] += 1
    else:
        rate[8] += 1
for tmp in range(len(rate)-1):
    if rate[tmp] > 0:
        factor += 1
    else:
        empty += 1
if rate[8] > 0:
    if factor == 0:
        print("1 "+str(rate[8])
    else:
        print(str(factor)+' '+str(factor+rate[8]))
else:
    print(str(factor)+' '+str(factor))

### FIXED CODE ###

# -*- coding:utf-8 -*-
N = int(input())
a = list(map(int, input().split()))
rate = [ 0 for tmp in range(9) ]
factor = 0
empty = 0
for tmp in range(N):
    if 1 <= a[tmp] and  a[tmp] <= 399:
        rate[0] += 1
    elif 400 <= a[tmp] and a[tmp] <= 799:
        rate[1] += 1
    elif 800 <= a[tmp] and a[tmp] <= 1199:
        rate[2] += 1
    elif 1200 <= a[tmp] and a[tmp] <= 1599:
        rate[3] += 1
    elif 1600 <= a[tmp] and a[tmp] <= 1999:
        rate[4] += 1
    elif 2000 <= a[tmp] and a[tmp]<= 2399:
        rate[5] += 1
    elif 2400 <= a[tmp] and a[tmp] <= 2799:
        rate[6] += 1
    elif 2800 <= a[tmp] and a[tmp] <= 3199:
        rate[7] += 1
    else:
        rate[8] += 1
for tmp in range(len(rate)-1):
    if rate[tmp] > 0:
        factor += 1
    else:
        empty += 1
if rate[8] > 0:
    if factor == 0:
        print("1 "+str(rate[8]))
    else:
        print(str(factor)+' '+str(factor+rate[8]))
else:
    print(str(factor)+' '+str(factor))
S = list(input())
T = list(input())
#S = list('??p??d??')
#T = list('abc')

Ns = len(S)
Nt = len(T)
flag = True
for i in range(Ns - Nt+1):
    for j in range(Nt):
        if not(S[i+j] == T[j] or S[i+j] == '?'):
            break
    else:
        flag = True
        break

if flag:
    
    ans = S
    for j in range(Nt):
        ans[i+j] = T[j]

    for k in range(Ns):
        if ans[k] == '?':
            ans[k] = 'a'
    ans = ''.join(ans)
else:
    ans = 'UNRESTORABLE'
    
print(ans)


### FIXED CODE ###


S = input()
T = input()
N = len(S)
K = len(T)

ans = []
flag = False
for i in range(N-K+1):
    for j in range(K):
        if not(S[i+j] == T[j] or S[i+j] == '?'):
            break
    else:
        flag = True
        tmp = list(S)
        for j in range(K):
            tmp[i+j] = T[j]
        for j in range(N):
            if tmp[j] == '?': tmp[j] = 'a'
        tmp = ''.join(tmp)
        ans.append(tmp)
        
if flag:
    ans.sort()
    print(ans[0])
else:
    print('UNRESTORABLE')
PDList = list(input())


for index, PD in enumerate(PDList):
    if PD != '?': continue

    if index == 1:
        if PDList[index + 1] == 'D' or PDList[index + 1] == '?': PDList[index] = 'P'
        else: PDList[index] = 'D'
        continue

    if PDList[index - 1] == 'P':
        PDList[index] = 'D'
        continue

    if PDList[index + 1] == 'D':
        PDList[index] = 'P'
        continue

    if PDList[index - 1] == 'D' and PDList[index + 1] == '?':
        PDList[index] = 'P'
        continue


    PDList[index] = 'D'
    continue


print(''.join(PDList))

### FIXED CODE ###

PDList = list(input())


for index, PD in enumerate(PDList):
    if PD != '?': continue

    if PD == '?' and len(PDList) == 1:
        PDList[index] = 'D'
        break

    if index == 0:
        if PDList[index + 1] == 'D' or PDList[index + 1] == '?': PDList[index] = 'P'
        else: PDList[index] = 'D'
        continue

    if PD == '?' and index == len(PDList) - 1:
        PDList[index] = 'D'
        continue


    if PDList[index - 1] == 'P':
        PDList[index] = 'D'
        continue

    if PDList[index + 1] == 'D':
        PDList[index] = 'P'
        continue

    if PDList[index - 1] == 'D' and PDList[index + 1] == '?':
        PDList[index] = 'P'
        continue


    PDList[index] = 'D'
    continue


print(''.join(PDList))
T = list(input())

if T[0] == '?':
    if T[1] == 'P':
        T[0] = 'D'
    else:
        T[0] = 'P'


for i in range(1, len(T)-1):
    if T[i] == '?':
        if T[i - 1] == 'D' and T[i + 1] == 'D':
            T[i] = 'P'
        else:
            T[i] = 'D'

if T[-1] == '?':
    T[-1] = 'D'

print(''.join(T))

### FIXED CODE ###

T = list(input())

if len(T) == 1:
    print('D')
    exit()

if T[0] == '?':
    if T[1] == 'P':
        T[0] = 'D'
    else:
        T[0] = 'P'


for i in range(1, len(T)-1):
    if T[i] == '?':
        if T[i - 1] == 'D' and (T[i + 1] == 'D' or T[i + 1] == '?'):
            T[i] = 'P'
        else:
            T[i] = 'D'

if T[-1] == '?':
    T[-1] = 'D'

print(''.join(T))
H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = [[0]*(W+1) for i in range(H+1)]
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l[x][y] = 1

c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if l[s][t] == 0:
      flag = True
      break
if flag:
  ans = c+d
else:
  ans = c+d-1
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = c+d
if not flag:
  ans -= 1
print(ans)
#Bingo
card = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
b = [int(input()) for _ in range(N)]
a = [[0]*3 for _ in range(3)]
for bi in b:
    for i in range(3):
        for j in raneg(3):
            if bi == card[i][j]:
                a[i][j] = 1
                
ans = 'No'
#tate
for i in range(3):
    if a[0][i] == 1 and a[1][i] == 1 and a[2][i] == 1:
        ans = 'Yes'
            
#yoko
for i in range(3):
    if a[i][0] == 1 and a[i][1] == 1 and a[i][2] == 1:
        ans = 'Yes'
    
#naname
if a[0][0] == 1 and a[1][1] == 1 and a[2][2] == 1:
    ans = 'Yes'
if a[1][3] == 1 and a[2][2] == 1 and a[3][1] == 1:
    ans ='Yes'
print(ans)

### FIXED CODE ###

#Bingo
card = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
b = list([int(input()) for _ in range(N)])
a = [[0]*3 for _ in range(3)]
for bi in b:
    for i in range(3):
        for j in range(3):
            if bi == card[i][j]:
                a[i][j] = 1
                
ans = 'No'
#tate
for i in range(3):
    if a[0][i] == 1 and a[1][i] == 1 and a[2][i] == 1:
        ans = 'Yes'
            
#yoko
for i in range(3):
    if a[i][0] == 1 and a[i][1] == 1 and a[i][2] == 1:
        ans = 'Yes'
    
#naname
if a[0][0] == 1 and a[1][1] == 1 and a[2][2] == 1:
    ans = 'Yes'
if a[0][2] == 1 and a[1][1] == 1 and a[2][0] == 1:
    ans ='Yes'
print(ans)
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[float('inf')]*(N+1)
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        if i+j>N-1:
            break
        else:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
print(dp[N-1])
 

### FIXED CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())

#dp[i][j]は、品数i,重さjのときの価値
dp =[[0 for i in range(W+1)] for j in range(N+1)] 
#表で表す

for i in range(N):#これは品数.i番目の品のオンオフ
    for j in range(W+1):#これは許容される重さの合計
        #選ぶ場合
        if j - w[i]>=0:
            dp[i+1][j]=max(dp[i][j],(dp[i][j-w[i]]+v[i]))
        #選ばない場合と比較
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])

print(dp[N][W])
s = input()
s.sort()
if s[0] == s[1] and s[2] == s[3]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = list(input())
s.sort()
if s[0] == s[1] and s[2] == s[3] and s[1] != s[2]:
    print("Yes")
else:
    print("No")
import sys


for line in sys.stdin:
    xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2 = map(float, line.split(' '))
    if ((xa1<=xb1 and xb1<=xa2) or (xb1<=xa1 and xa1<=xb2)) and ((yb1<=ya2 and ya2<=yb2) or (ya1<=yb2 and yb2<=ya2)):
        print 'YES'
    else:
        print 'NO'

### FIXED CODE ###


import sys


for line in sys.stdin:
    xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2 = map(float, line.strip().split(' '))
    if ((xb1<=xa1 and xa1<=xb2) or (xa1<=xb1 and xb1<=xa2)) and ((yb1<=ya2 and ya2<=yb2) or (ya1<=yb2 and yb2<=ya2)):
        print 'YES'
    else:
        print 'NO'
import math
n,k= map(int,input().split())
m=min(n,k)
a=[0]*n
for i in range(1,m+1):
    a[i-1]=math.ceil(math.log2(k/i))
for i in range(m):
    a[i]=0.5**a[i]
print((sum(a)+max(n-k,0))/n)

### FIXED CODE ###

import math
n,k= map(int,input().split())
m=min(n,k)
a=[0]*n
for i in range(1,m+1):
    a[i-1]=math.ceil(math.log2(k/i))
for i in range(m):
    a[i]=0.5**a[i]
print((sum(a)+max(n-k,0))/n)
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
s = sum(A)
 
print( max(N - A, -1) )

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
 
s = sum(A)
 
print( max(N - s, -1) )
a,b,n = map(int,input().split())
c = n // b * b
ans=0
if n > b - 1:
    ans = math.floor(a * c / b) - a * math.floor(c / b)

else:
    #for i in range(n):
        #print(i+1)
        #print(math.floor(a * (i+1) / b) - a * math.floor((i+1) / b))
        #if math.floor(a * (i+1) / b) - a * math.floor((i+1) / b) > ans:
        #    ans = math.floor(a * (i+1) / b) - a * math.floor((i+1) / b)
    ans = math.floor(a * n / b) - a * math.floor(n / b)
print(ans)
    

### FIXED CODE ###

#copy
import math
a, b, n = list(map(int, input().split()))
x = min(b-1,n)
ans = math.floor(a*x/b)-a*math.floor(x/b)
print(ans)
INT_MAX = 10**8
h, n = map(int, input().split())
e = tuple(tuple(map(int, input().split())))

dp = [0] + [INT_MAX]* h
for i in range(1, h+1):
  for a, b in e:
    c = dp[max(0, i - a)] + b
    dp[i] = min(dp[i], c)

print(dp[h])

### FIXED CODE ###

INT_MAX = 10**8
h, n = map(int, input().split())
e = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [INT_MAX] * (h+1)
dp[0] = 0
for i in range(1, h+1):
  for a, b in e:
    c = dp[max(0, i - a)] + b
    dp[i] = min(dp[i], c)

print(dp[h])
from collections import Counter

N, K = list(map(int,input().split()))
H = []
for i in range(N):
    H.append(int(input()))
H = sorted(H,reverse = False)
C = Counter(H)
CH = list(C.values()) 

cnt = 0
for i in range(len(CH)):
    if CH[i] >= K:
        cnt += 1
        break
if cnt != 0:
    print('0')
else:
    #print(H[K-1] - H[0])
    print(min(H[K-1] - H[0],H[K] - H[1],H[K+1] - H[2]))

### FIXED CODE ###

from collections import Counter

N, K = list(map(int,input().split()))
H = []
for i in range(N):
    H.append(int(input()))
H = sorted(H,reverse = False)
C = Counter(H)
CH = list(C.values()) 

cnt = 0
for i in range(len(CH)):
    if CH[i] >= K:
        cnt += 1
        break
ans = 999999999999999
for i in range(N-K+1):
    ans = min(ans,H[K-1+i] - H[i]) 

if cnt != 0:
    print('0')
else:
    print(ans)
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
def nli(x):return [input for _ in range(x)]
def hukusuu(): 
  listA=[] #appendのために宣言が必要
  while True:
    try:listA.append(list(map(int,input().split())))
    except:break #または、quit(),os.exit()をして止める。
  return listA

n,k=ma()
h=rli()

from itertools import accumulate , groupby as acc , gp
import operator as op
import copy as cp
import math
from bisect import bisect_left as bisl
from bisect import bisect_right as bisr
def ifif(s):
  if s:print("Yes")
  else:print("No")

h.sort()
inde=bisl(h,k)
print(n-inde)  




### FIXED CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
def nli(x):return [input for _ in range(x)]
def hukusuu(): 
  listA=[] #appendのために宣言が必要
  while True:
    try:listA.append(list(map(int,input().split())))
    except:break #または、quit(),os.exit()をして止める。
  return listA

n,k=ma()
h=rli()

from itertools import accumulate as acc 
import operator as op
import copy as cp
import math
from bisect import bisect_left as bisl
from bisect import bisect_right as bisr
def ifif(s):
  if s:print("Yes")
  else:print("No")

h.sort()
inde=bisl(h,k)
print(n-inde)
a, b, k = map(int, input().split())
l = []

for i in range(1,n+1):
    if a % i == 0 and b % i == 0:
        l.append(i)
        
print(l[k-1])
    

### FIXED CODE ###

a, b, k = map(int, input().split())
l = []

for i in range(1,min(a,b)+1):
    if a % i == 0 and b % i == 0:
        l.append(i)
        
print(list(reversed(l))[k-1])
S = input()
t = [x for i in range(len(s))]
print(*t)

### FIXED CODE ###

S = input()
t = ["x" for i in range(len(S))]
print("".join(t))
from fraction import gcd
def swap(a,b):
  c=a
  a=b
  b=c
  return(a,b)
n,m=map(int,input().split())
s=input()
t=input()
o=n*m//gcd(n,m)
if m>n:
  s,t=swap(s,t)
  n,m=swap(n,m)
if not n%m:
  for i in range(m):
    if s[n//m*i]!=t[i]:
      print(-1)
      break
  else:
    print(n)
  exit()
for i in range(1,10**7):
  g=o*i
  x=['.']*g
  for j in range(n):
    x[j*(g//n)]=s[j]
  for j in range(m):
    if x[j*(g//m)]!='.'and x[j*(g//m)]!=t[j]:break
  else:
    print(len(x))
    break
else:print(-1)

### FIXED CODE ###

from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
a=n//g
b=m//g
for i in range(g):
  if s[a*i]!=t[b*i]:
    print(-1)
    break
else:
  print(n*m//g)
n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,k=map(int,input().split())
    s.append([l for l in range(j,k+1)])
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
s.sort()
for i in range(1,n):
    tmp=0
    for j in s:
        if i-j[0]<0:
            break
        else:
            tmp+=sum(pattern[max(i-j[1],0):i-j[0]])
        tmp%=INF
    pattern[i]=tmp
print(pattern[-1])

### FIXED CODE ###

n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,jj=map(int,input().split())
    s.append([l for l in range(j,jj+1)])
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
memo=[0 for i in range(k)]
s.sort()
for i in range(1,n):
    tmp=0
    for index,j in enumerate(s):
        if i-j[0]<0:
            break
        elif i-j[-1]>0:
            memo[index]+=pattern[i-j[0]]
            memo[index]-=pattern[i-j[-1]-1]
            if memo[index]<0:
                memo[index]+=INF
        else:
            memo[index]+=pattern[i-j[0]]

        #tmp+=sum(pattern[max(i-j[-1],0):i-j[0]+1])
        memo[index]%=INF
    pattern[i]=(sum(memo)%INF)
print(pattern[-1])
import sys

S, K = [int(i) for i in input()], int(input())

if S[0] == 1:
    for i in range(1, len(S)):
        if S[i] == 1:
            pass
        else:
            idx = i
            break
else:
    print(S[0])
    sys.exit()

if K-1 < idx:
    print(1)
else:
    print(S[idx])


### FIXED CODE ###

import sys

S, K = [int(i) for i in input()], int(input())

if S[0] == 1:
    length = 1
    for i in range(1, len(S)):
        if S[i] == 1:
            length += 1
            pass
        else:
            idx = i
            break
else:
    print(S[0])
    sys.exit()

if len(S) == length:
    print(1)
else:
    if K-1 < idx:
        print(1)
    else:
        print(S[idx])
a, b = map(int, input().split())
if (a*b) % 2:
  ptint('Odd')
else:
  print('Even')


### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
import sympy

N = sympy.factorint(int(input()))

key = list(N.keys())
val = list(N.values())

sum = 0
for i in range(len(key)):
    count = 1
    length = val[i]
    if (length < 3):
        sum += 1
    else:
        while(length > 0):
            sum += 1
            length -= count
            count += 1

print(sum)


### FIXED CODE ###

import math
#試し割法
def trial_division(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = trial_division(int(input()))

key = []
val = []

dupli = set()
for i in range(len(N)):
    if (not N[i] in dupli):
        key.append(N[i])
        dupli.add(N[i])

for i in range(len(key)):
    val.append(N.count(key[i]))


def maxvalue(n):
    if (n < 3):
        return 1
    elif (n < 6):
        return 2
    elif (n < 10):
        return 3
    elif (n < 15):
        return 4
    elif (n < 21):
        return 5
    elif (n < 28):
        return 6
    elif (n < 36):
        return 7
    elif (n < 45):
        return 8
    elif (n < 55):
        return 9
    elif (n < 66):
        return 10

sum = 0
for i in range(len(key)):
    sum += maxvalue(val[i])
    # count = 1
    # length = val[i]
    # if (length < 3):
    #     sum += 1
    # else:
    #     while(length > 0):
    #         sum += 1
    #         length -= count
    #         if (length == count):
    #             break
    #         count += 1

print(sum)