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

import copy

h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = [[False]*w for _ in range(h)]
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
                    cnt += 1
    if cnt > 0:
        c = copy.deepcopy(tmp)
        ans += 1
    else:
        break

print(ans)


### FIXED CODE ###

import copy
#import time

h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = [[False]*w for _ in range(h)]
#s = time.time()
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))
#print(time.time()-s)

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
                    cnt += 1
    #print(time.time()-s)
    if cnt > 0:
        c = copy.copy(tmp)
        ans += 1
    else:
        break
    #print(time.time()-s)

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

import bisect
import sys

inf = sys.maxsize
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

for i in range(M):
    x = A.pop(N-1)
    if x == 0:
        break
    x = x // 2
    A.insert(bisect.bisect_left(A, x), x)
print(sum(A))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    x = int(x / 2)
    heapq.heappush(A, x)  # pop minimum
print(-sum(A))
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 0

for n in c.items():
  if n[1] > 1:
    total += n[1]*(n[1]-1)//2

for i in range(N):
  ans = total
  ans -= A.count(A[i])-1
  print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-c[A[i]])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    hmax = H + max(A)
    cost = [0] * hmax
    intmax = 99999
    magics = [(a, b) for a, b in zip(A,B)]
    for i in range(1, hmax):
        for a, b in magics:
            if i >= a:
                cost[i] = min(cost[i-a]+b, cost[i]) if cost[i] > 0 else cost[i-a]+b
            else:
                cost[i] = min(b, cost[i]) if cost[i] > 0 else b
    #print(cost)
    print(min(cost[H:]))

def solve_dijkstra(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

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

def main2():
    N = int(input().strip())
    r_stack=[]
    stack=[]
    for n in input().split():
        n = int(n)
        if len(r_stack)==0:
            stack.append(n)
            r_stack.append(n)
        elif len(r_stack)%2!=0:
            stack.append(n)
            r_stack.insert(0,n)
        else:
            stack.insert(0,n)
            r_stack.append(n)
    if N % 2 ==0:
        ans_list=[str(num) for num in r_stack]
        ans=' '.join(ans_list)
    else:
        ans_list=[str(num) for num in stack]
        ans=' '.join(ans_list)
    print(ans)

if __name__ == "__main__":
    main2()

### FIXED CODE ###

from collections import deque
def main3():
    d = deque()
    rd= deque()
    N = int(input().strip())
    for n in input().split():
        if len(rd)%2!=0:
            d.append(n)
            rd.appendleft(n)
        else:
            rd.append(n)
            d.appendleft(n)
    if N % 2 ==0:
        print(*rd)
    else:
        print(*d)

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

n=int(input())
ans=0
for i in range(1,n+1):
    a=i
    for j in range(2,1+int(i**.5)):
        b=0
        while i%j==0:
            i//=j
            b+=1
        a*=b+1
    if i!=1:
        a*=2
    ans+=a
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    a=n//i
    ans+=i*a*(a+1)//2
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
where_go = list(map(int, input().split()))
now = 0
PATH = []
start = 0
roop = 0
count = 0

while now not in PATH and count < K:
    PATH.append(now)
    now = where_go[now] -  1
    count += 1

if count < K:
    start = PATH.index(now)
    roop = len(PATH) - start
    K = (K - start) % roop
    count = 0
    while count < K:
        now = where_go[now] -  1
        count += 1

print(now+1)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split())) #どこに行くかのリスト
now = 0 #どこにいるか
LOG = {}
roop = 0
count = 0

while now not in LOG and count < K:
    LOG.setdefault(now, count)
    now = A[now] -  1
    count += 1

if count < K:
    roop = len(LOG) - LOG[now]
    K = (K - count) % roop
    count = 0
    while count < K:
        now = A[now] -  1
        count += 1

print(now+1) #行った場所を保存
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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

DISHES = [(0, 0)]
for _ in range(n):
    a, b = map(int, input().split())
    DISHES.append((a, b))
DISHES.sort()

DP = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, t + 1):
        a, b = DISHES[i][0], DISHES[i][1]
        if j - a < 0:
            DP[i][j] = DP[i - 1][j]
        else:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - a] + b)

answer = 0
for k in range(1, n + 1):
    happiness_k = DP[k - 1][t - 1] + DISHES[k][1]
    if happiness_k > answer:
        answer = happiness_k

print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline


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

DISHES = [(0, 0)]
for _ in range(n):
    a, b = map(int, input().split())
    DISHES.append((a, b))
DISHES.sort()

DP = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    a, b = DISHES[i]
    for j in range(1, t + 1):
        if j - a < 0:
            DP[i][j] = DP[i - 1][j]
        else:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - a] + b)

answer = 0
for k in range(1, n + 1):
    answer = max(answer, DP[k - 1][t - 1] + DISHES[k][1])

print(answer)
### BUGGY CODE ###

A=[]
for _ in range(int(input())):
    i = int(input())
    if i in A:
        A.remove(i)
    else:
        A.append(i)
        
print(len(A))

### FIXED CODE ###

n=int(input())
d={}
for _ in [0]*n:
    v=int(input())
    d[v]=(d.get(v,0)+1)%2
    
print(sum(d.values()))
### BUGGY CODE ###

X=int(input())

def factorization(n):
    cnt=0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt+=1
            if i != n // i:
                cnt+=1
        i += 1
    return cnt
  
answer=0
for k in range(1,X+1):
  answer+= k*factorization(k)
  
print(answer)

### FIXED CODE ###

n=int(input())

answer=0
for x in range(1,n+1):
  y=n//x
  answer+=y*(y+1)*x/2
print(int(answer))
### BUGGY CODE ###

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

if 0 in a:
    print(0)
else:
    for i in range(len(a)):
        ans *= a[i]
    if ans > (10**18):
        print(-1)
    else:
        print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 1

if 0 in a:
    print(0)
else:
    for i in range(len(a)):
        ans *= a[i]
        if ans > (1000000000000000000):
            print(-1)
            sys.exit()
    else:
        print(ans)
### BUGGY CODE ###

from collections import deque
X, Y, Z, K = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

out = deque()
out2 = deque()

for i in range(X):
    for j in range(Y):
        out.append(A[i]+B[j])
out = sorted(out, reverse=True)
del out[K:]
for i in range(len(out)):
    for j in range(Z):
        out2.append(out[i]+C[j])
out2 = sorted(out2, reverse=True)
for i in range(K):
    print(out2[i])


### FIXED CODE ###

from collections import deque
X, Y, Z, K = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

out = deque()
out2 = deque()

for i in range(X):
    for j in range(Y):
        out.append(A[i]+B[j])
out = sorted(out, reverse=True)
del out[K:]
for i in range(len(out)):
    for j in range(Z):
        out2.append(out[i]+C[j])
out2 = sorted(out2, reverse=True)
for i in range(K):
    print(out2[i])
### BUGGY CODE ###

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

ct = [0] * (2*10**5+1)
ans = [0] * (n+1)

for i in range(len(la)):
    ct[la[i]] += 1

sa = set(la)

for j in sa:
    ans[j] = ct[j] * (ct[j]-1) // 2

# print(ct[0:10])
# print(ans)

for k in range(n):
    knum = la[k]
    ans[knum] = (ct[knum] - 1) * (ct[knum] - 2) // 2
    print(sum(ans))
    ans[knum] = (ct[knum] - 1) * ct[knum] // 2


### FIXED CODE ###

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

ct = [0] * (2*10**5+1)
ans = [0] * (n+1)
ld = [0] * (n+1)

for i in range(len(la)):
    ct[la[i]] += 1

sa = set(la)

for j in sa:
    ans[j] = ct[j] * (ct[j]-1) // 2
    ld[j] = ans[j] - ((ct[j]-2) * (ct[j]-1) // 2)

total = sum(ans)

# print(ct[0:10])
# print(ans)

for k in range(n):
    knum = la[k]
    print(total - ld[knum])
### BUGGY CODE ###

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7

sum_list =[p[i]*p[t] for i in range(a) for t in range(a) if i<=t and not i ==t]
print(sum(sum_list)%mod)

### FIXED CODE ###

import itertools as itr

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7
ans =0
sum_list = list(itr.accumulate(p))
for i in range(len(p)-1):
    o = p[i+1]
    w =sum_list[i]
    ans = (ans+o*w%mod)%mod
print(ans)
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
        else:
            count += 1
            if count > k :
                return False
            tmpList = []
            tmpList.append(x)
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    #dp[v] vとなる最小のＷ
    dp = [10**9+1 for _ in range(10**5+1)]
    for _ in range(N):
        w,v = map(int, input().split())
        for val in range(10**5, 1, -1):
            if val - v < 1:
                break
            dp[val] = min(dp[val], dp[val - v] + w)
        if dp[v] > w:
            dp[v] = w
    ans = 0
    for v, w in enumerate(dp):
        if w <= W:
            ans = max(ans, v)
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    #dp[v] vとなる最小のＷ
    dp = [10**9+1 for _ in range(10**5+1)]
    for _ in range(N):
        w,v = map(int, input().split())
        for val in range(10**5, 1, -1):
            if val - v < 1:
                break
            dp[val] = min(dp[val], dp[val - v] + w)
        if dp[v] > w:
            dp[v] = w
    ans = 0
    for v, w in enumerate(dp):
        if w <= W:
            ans = max(ans, v)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def resolve():
    n = int(input())
    dict = {}
    s = ["".join(sorted(input())) for _ in range(n)]
    for i in range(n):
        if s[i] in dict.keys():
            dict[s[i]] += 1
        else:
            dict[s[i]] =1
    alist = list (dict.values())
    ans = 0
    for i in range(len(alist)):
        ct = alist[i]
        ans += (ct*(ct-1))//2
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    s = [",".join(sorted(input())) for i in range(n)]
    ans = {}
    count = 0
    for i in range(n):
        if s[i] in ans:
            count += ans[s[i]]
            ans[s[i]] += 1
        else:
            ans[s[i]] = 1
    print(count)
resolve()
### BUGGY CODE ###

import sys
import heapq
N,M=map(int,input().split())
alist=list(map(int,input().split()))

cblist=[]
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
cblist.sort(reverse=True)

hq=[]
for a in alist:
  heapq.heappush(hq,a)
  
for C,B in cblist:
  for i in range(B):
    if C<hq[0]:
      print(sum(hq))
      sys.exit(0)
    else:
      heapq.heapreplace(hq,C)
else:
  print(sum(hq))

### FIXED CODE ###

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

alist.sort()
cblist = []
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
  
cblist.sort(reverse=True)
#print(alist)
#print(cblist)

index = 0
for (C,B) in cblist:
  for i in range(index,index+B):
    if i == len(alist):
      break
    
    if alist[i] < C:
      alist[i] = C
    else:
      break
      
  index += B
  if index >= len(alist):
    break
  
#print(alist)
print(sum(alist))
### BUGGY CODE ###

n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d={i:a.count(i) for i in set(a)}
p=len(d)-k
if p>0: print(sum((t[1] for t in sorted(d.items(), key=lambda x:x[1])[:p])))
else: print("0")


### FIXED CODE ###

n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d={i:0 for i in set(a)}
for i in a: d[i]+=1
print(n-sum([t[1] for t in sorted(d.items(), key=lambda x:-x[1])][:k]))
### BUGGY CODE ###

s = input()
t = input()

dp = [0] * (len(s)+1)
dps = [[] for _ in range(len(s)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    for j in range(1, len(s)+1):
        sj = s[j-1]
        if ti == sj:
            dp[j] = dp[j-1] + 1
            dps[j] = (dps[j-1] + [ti]).copy()
        else:
            if dp[j-1] >= dp[j]:
                dp[j] = dp[j-1]
                dps[j] = dps[j-1][:]
print(''.join(dps[-1]))

### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1][:]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)
### BUGGY CODE ###

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

dp = [10**9]*N
dp[0] = 0

for i in range(1,N):
  for j in range(1,K+1):
    if i-j >= 0:
      dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[N-1])

### FIXED CODE ###

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

dp = [10**9]*N
dp[0] = 0

for i in range(1,N):
  for j in range(K+1):
    if i-j >= 0:
      dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
  
print(dp[N-1])
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    i = i + 1
    for j in range(N-i):
        j = i + j + 1
        if S[i-1] == S[j-1]:
            continue
        for k in range(N-j):
            k = k + j + 1
            if S[j-1] != S[k-1] and S[i-1] != S[k-1]:
                if j-i != k-j:
                    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
T = [0]*3

for i in range(N):
    if S[i] == "R":
        T[0] += 1
    elif S[i] == "G":
        T[1] += 1
    else:
        T[2] += 1
ans = T[0]*T[1]*T[2]
t = N // 2

for i in range(t):
    i = i+1
    j = 0
    while j + 2*i < N:
        if S[j] != S[j + i] and S[j] != S[j + 2*i] and S[j+i] != S[j + 2*i]:
            ans -= 1
        j += 1

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

A, B, N = map(int, input().split())
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]

if N < B:
    a = int(A * N / B)
    b = A * int(N / B)
    print(a - b)
    exit(0)

ans = 0
before_ans = 0
for i in range(1, N + 1):
    a = int(A * i / B)
    b = A * int(i / B)
    ans = max(ans, a - b)
    if before_ans > a - b:
        break
    if ans == min(A - 1, B - 1):
        break
    before_ans = a - b
print(ans)

### FIXED CODE ###

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


# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
def solve(i):
    a = int(A * i / B)
    b = A * int(i / B)
    return a - b


print(solve(min(N, B - 1)))
### BUGGY CODE ###

N = float(input())
q = N
r_s = []
while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  r_s.append(r)
r_s.append(1)
r_s = r_s[::-1]
for i in range(len(r_s)):
  print(r_s[i], end="")

### FIXED CODE ###

N = float(input())

if N==0:
  print(0)
else:
  q = N
  r_s = []

  while q!=1:
    hoge = (q-1) / (-2)
    if hoge.is_integer():
      r = int(1)
      q = float(hoge)
    else:
      r = int(0)
      q = float(q/(-2))
  
    r_s.append(r)
  r_s.append(1)
  r_s = r_s[::-1]

  for i in range(len(r_s)):
    print(r_s[i], end="")
### BUGGY CODE ###

h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=[],[]
rs.append(sr-1)
cs.append(sc-1)
magic=[[1e6 for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.pop(0),cs.pop(0)
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.append(nr)
            cs.append(nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)

### FIXED CODE ###

import collections

h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=collections.deque([sr-1]),collections.deque([sc-1])
magic=[[1e6 for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.popleft(),cs.popleft()
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.appendleft(nr)
            cs.appendleft(nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)
### BUGGY CODE ###

import sys
n=int(input())
if n==1:
    print(0)
    sys.exit()
def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
tmp=f(n)
ans=0
for i in tmp:
    dd=i[1]
    tt=1
    while dd>0:
        if dd-tt>=0:
            dd-=tt
            tt+=1
            ans+=1
print(ans)

### FIXED CODE ###

import sys
n=int(input())
if n==1:
    print(0)
    sys.exit()
def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
tmp=f(n)
ans=0
for i in tmp:
    dd=i[1]
    tt=1
    while dd>0:
        if dd-tt>=0:
            dd-=tt
            tt+=1
            ans+=1
        else:
            break
print(ans)