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

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())

n = I()
s = list(S())

ans = 0
for i in range(n-2):
    color = {s[i]}
    for j in range(i+1,n-1):
        if not s[j] in color:
            color.add(s[j])
            for k in range(j+1,n):
                if not s[k] in color:
                    if i+k-2*j:
                        ans += 1
            color = {s[i]}

print(ans)

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())

r = s.count('R')
g = s.count('G')
b = s.count('B')
 
ans = r*g*b
for i in range(n-1):
    for j in range(1,n):
        if i-j<0 or n<=i+j:
            break
        else:
            if s[i-j]!=s[i] and s[i]!=s[i+j] and s[i-j]!=s[i+j]:
                ans-=1
 
print(ans)
### BUGGY CODE ###

import math

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

lcm = a[0]
pwise_flag = True
for i in range(1,n):
    gcd = math.gcd(lcm,a[i])
    if gcd != 1:
        pwise_flag = False
        break
    else:
        lcm = lcm*a[i]
        
if pwise_flag:
    print('pairwise coprime')
else:
    min_a = min(a)
    swise_flag = False
    
    pf={}
    for i in range(2,int(min_a**0.5)+1):
        while min_a%i==0:
            pf[i]=pf.get(i,0)+1
            min_a//=i
    if min_a>1:pf[min_a]=1
    
    
    for i in range(n):
        del_keys = []
        for prime in pf.keys():
            if a[i]%prime != 0:
                del_keys.append(prime)
        for i in del_keys:
            del pf[i]
    
    if pf.keys():
        print('not coprime')
    else:
        print('setwise coprime')

### FIXED CODE ###

import math

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

MAX = 1000005
c = [0]*MAX

for i in range(n):
  c[a[i]] += 1

pair = True

for i in range(2,MAX):
  cnt = 0
  for j in range(i,MAX,i):
    cnt += c[j]
  if cnt > 1:
    pair = False

if pair:
  print('pairwise coprime')
else:
  g = a[0]
  for i in range(1,n):
    g = math.gcd(g,a[i])
    
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')
### BUGGY CODE ###

h,w,d=[int(i) for i in input().split()]
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a0 =[int(i0) for i0 in input().split()]
  a.append(a0)
  for j in range(w):
    p[a0[j]]=[i,j]

n=int(input())

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

@lru_cache(maxsize=1000)
def dist_d(s,g,d):
  if s==g:
    return 0
  else:
    y0,x0=p[s]
    s = a[y0][x0]+d
    y,x = p[s]
    return abs(x-x0)+abs(y-y0) + dist_d(s,g,d)
  
for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
 
  print(dist_d(s,g,d))

### FIXED CODE ###

I=lambda:map(int,input().split())
h,w,d=I()
H={}
W={}
for i in range(1,h+1):
  for j,k in enumerate(I(),1):
    H[k],W[k]=i,j
x=1+h*w
s=[0 for _ in range(x)]
for i in range(d+1,x):
  s[i]=s[i-d]+abs(H[i]-H[i-d])+abs(W[i]-W[i-d])

for _ in range(int(input())):
  a,b=I()
  print(s[b]-s[a])
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = [0]+LIST()
a_acc = list(accumulate(a))

@lru_cache(maxsize=None)
def rec(l, r):
    if l == r:
        return 0
    mi = INF
    for i in range(l, r):
        mi = min(mi, rec(l, i)+rec(i+1, r))
    return mi + (a_acc[r]-a_acc[l-1])

print(rec(1, N))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = [0]+LIST()
a_acc = list(accumulate(a))
dp = [[None]*(N+1) for _ in range(N+1)]

def rec(l, r):
    if dp[l][r]: return dp[l][r] 
    if l == r:
        return 0
    mi = INF
    for i in range(l, r):
        mi = min(mi, rec(l, i)+rec(i+1, r))
    dp[l][r] = mi + (a_acc[r]-a_acc[l-1])
    return dp[l][r]

print(rec(1, N))
### BUGGY CODE ###

Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
prime2 = primes(maxr)
prime = [i for i in prime2 if (i+1)/2 in prime2]
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))

### FIXED CODE ###

Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(3,n + 1) if is_prime[i] and is_prime[(i+1)//2]]
prime = primes(maxr)
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))
### BUGGY CODE ###

def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7 #素数
    
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res
    
    def cmb(n, r, mod):
        # 分子(n*(n-1)*...*(n-r+1))
        nume = 1
        for i in range(n-r+1, n+1):
            nume = nume * i# % mod
        # 分母（1*2*...*r）
        deno = 1
        for j in range(1, r+1):
            deno = deno * j % mod
        d = modpow(deno, mod-2, mod)
        return nume * d % mod
    
    all_cmb = pow(2, n, mod) - 1
    bad_a = cmb(n, a, mod)
    bad_b = cmb(n, b, mod)    
    print((all_cmb-bad_a-bad_b) % mod)

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7 #素数
    
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res
    
    def cmb(n, r):
        # 分子(n*(n-1)*...*(n-r+1))
        nume = 1
        for i in range(n-r+1, n+1):
            nume = nume * i % mod
        # 分母（1*2*...*r）
        deno = 1
        for j in range(1, r+1):
            deno = deno * j % mod
        d = modpow(deno, mod-2, mod)
        return nume * d
    
    all_cmb = pow(2, n, mod) - 1
    bad_a = cmb(n, a)
    bad_b = cmb(n, b)    
    print((all_cmb-bad_a-bad_b) % mod)

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

from collections import deque
H, W = map(int, input().split())

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()

for i in range(H):
    for j in range(W):
        if area[i][j] == "#":
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0

didj = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0

while len(to_search) > 0:
    nowi, nowj, nowd = to_search.pop()
    for di, dj in didj:
        nexti = nowi + di
        nextj = nowj + dj
        if 0 <= nexti < H and 0 <= nextj < W:
            if distance[nexti][nextj] > nowd + 1:
                to_search.appendleft((nexti, nextj, nowd + 1))
                distance[nexti][nextj] = nowd + 1
                ans = max(ans, nowd + 1)

print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()

for i in range(H):
    for j in range(W):
        if area[i][j] == "#":
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0

didj = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0

while len(to_search) > 0:
    nowi, nowj, nowd = to_search.pop()
    for di, dj in didj:
        nexti = nowi + di
        nextj = nowj + dj
        if 0 <= nexti < H and 0 <= nextj < W:
            if distance[nexti][nextj] > nowd + 1:
                to_search.appendleft((nexti, nextj, nowd + 1))
                distance[nexti][nextj] = nowd + 1
                ans = max(ans, nowd + 1)

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

N = int(input())


for n in range(1,N+1):
    cnt = 0
    for x in range(1,105):
        for y in range(1, 105):
            for z in range(1, 105):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    cnt +=1
    print(cnt)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i*i+j*j+k*k+i*j+j*k+k*i;
            if v<10050:
                ans[v]+=1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

import collections


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
cnt = collections.Counter(A)
for i in range(Q):
    BC = list(map(int, input().split()))

    if BC[0] in cnt:
        if BC[1] in cnt:
            cnt[BC[1]] += cnt[BC[0]]
            del cnt[BC[0]]
        else:
            cnt[BC[1]] = cnt[BC[0]]
            del cnt[BC[0]]

    s = 0
    for k, v in cnt.items():
        s += int(k) * v
    print(s)


### FIXED CODE ###

import collections


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
cnt = collections.Counter(A)

s = 0
for k, v in cnt.items():
    s += int(k) * v
for i in range(Q):
    BC = list(map(int, input().split()))

    if BC[0] in cnt:
        if BC[1] in cnt:
            cnt[BC[1]] += cnt[BC[0]]
            s += int(BC[1]) * cnt[BC[0]]
            s -= int(BC[0]) * cnt[BC[0]]
            del cnt[BC[0]]
        else:
            cnt[BC[1]] = cnt[BC[0]]
            s += int(BC[1]) * cnt[BC[0]]
            s -= int(BC[0]) * cnt[BC[0]]
            del cnt[BC[0]]
    print(s)
### BUGGY CODE ###

# coding: utf-8

N = int(raw_input())

for h in range(1, 3501):
    for n in range(1, 3501):
        for w in range(1, 3501):
            if 4 * h * n * w == N * n * w + N * h * w + N * h * n:
                print h, n, w
                exit()


### FIXED CODE ###

def solver():
    N = int(raw_input())

    for h in xrange(1, 3501):
        for n in xrange(1, 3501):
            x = N * h * n;
            y = 4 * n * h - N * n - N * h;
            if y > 0 and x % y == 0:
                w = x / y
                return map(str, [h, n, w])


print " ".join(solver())
### BUGGY CODE ###

import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            if not dpu:
                dpu = dfs(v)
            else:
                dpv = dfs(v)
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        for d in range(len(dpu)):
            u0, u1, u2 = dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()
### BUGGY CODE ###

from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        a,b=map(len,algorithms.bipartite.sets(s:=g.subgraph(c)))
        x+=a*b-len(s.edges)
    print(x)
main()

### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))
### BUGGY CODE ###


n = int(input())


def func(times):
    power = 1
    divide_num = 10 ** 9 + 7

    for i in range(times):
        power *= (i + 1)

    print(power % divide_num)


func(times=n)


### FIXED CODE ###


n = int(input())


def func(times):
    power = 1
    divide_num = 10 ** 9 + 7

    for i in range(times):
        power *= (i + 1)
        power %= divide_num

    print(power)


func(times=n)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(a) for a in input().split()]
A.sort()
for _ in range(M):
  count = 1
  B,C = map(int,input().split())
  while min(A) < C and count <= B:
    A[0] = C
    A.sort()
    count += 1
print(sum(A))
    

    


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a) > 2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    S[i] = sorted(S[i])

count = 0

for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            count += 1

print(count)

### FIXED CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    S[i] = sorted(S[i])

S = sorted(S)
count = 0

a = [1]
for i in range(N-1):
    if S[i] == S[i+1]:
        a[-1] += 1
    else:
        a.append(1)
    
for i in range(len(a)):
    count += a[i]*(a[i]-1)/2
        
count = int(count)
        
print(count)
### BUGGY CODE ###

s = input()
q = int(input())

flag_swap = False
for i in range(q):
  query = list(input().split())
  if query[0] == "1":
    flag_swap = not flag_swap
  else:
    if (query[1] == "1" and not flag_swap) or (query[1] == "2" and flag_swap):
      s = query[2] + s
    else:
      s += query[2]

idx = range(len(s))
if flag_swap:
  idx = reversed(idx)
for i in idx:
  print(s[i], end="")
  
      
      

### FIXED CODE ###

s = input()
q = int(input())
left = ""
right = ""
flag_swap = False
for i in range(q):
  query = list(input().split())
  if query[0] == "1":
    flag_swap = not flag_swap
  else:
    if (query[1] == "1" and not flag_swap) or (query[1] == "2" and flag_swap):
      left += query[2]
    else:
      right += query[2]

if flag_swap:
  print(right[::-1]+s[::-1]+left)
else:
  print(left[::-1]+s+right)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    ans = 0
    index = 0

    for i in range(N):
        s2 = S[i+1:N]
        for j in range(i+1-index):
            s1 = S[index+j:i+1]
            if len(s1) < ans:
                break
            if s1 in s2:
                index = index+j
                ans = len(s1)
                break
        if len(s2) <= ans:
            break

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ans = 0
    index = 0

    for i in range(N):
        s1 = S[index:i+1]
        s2 = S[i+1:]
        if s1 in s2:
            ans = len(s1)
        else:
            index += 1

    print(ans)

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

N,X,Y=map(int,input().split())
count=[0]*(N-1)
for i in range(1,N+1):
    for j in range(i+1,N+1):
        d=[]
        d.append(abs(j-i))
        d.append(abs(X-i)+1+abs(j-Y))
        d.append(abs(Y-i)+1+abs(j-X))
        count[min(d)-1]+=1
for k in count:
    print(k)

### FIXED CODE ###

N,X,Y=map(int,input().split())
count=[0]*(N-1)
for i in range(1,N):
    for j in range(i+1,N+1):
        num=min(abs(j-i),abs(X-i)+1+abs(j-Y),abs(Y-i)+1+abs(j-X))
        #d=[]
        
        #d.append(abs(j-i))
        #d.append(abs(X-i)+1+abs(j-Y))
        #d.append(abs(Y-i)+1+abs(j-X))
        count[num-1]+=1
for k in count:
    print(k)
### BUGGY CODE ###

import sys
n,k = [int(i) for i in input().split()]

steps = [int(i) for i in input().split()]
dp = [999999] * n

if n <= k:
    print(abs(steps[0] - steps[n-1]))
    sys.exit()

for i in range(k):
    dp[i] = abs(steps[0] - steps[i])

for i in range(k, n):
    temp = []
    for j in range(1, k + 1):
            temp.append(dp[i-j] + abs(steps[i] - steps[i-j]))
    dp[i] = min(temp)

print(dp[n-1])

### FIXED CODE ###

import numpy as np
 
 
N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])
 
dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()
 
print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3

import collections


def solve(n, t, xs):
    trades = collections.defaultdict(int)
    for i in range(n):
        for j in range(i + 1, n):
            delta = xs[j] - xs[i]
            if delta > 0:
                trades[delta] += 1
    max_delta = max(trades.keys())
    return trades[max_delta]


def main():
    n, t = map(int, input().split())
    xs = list(map(int, input().split()))
    print(solve(n, t, xs))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3

import collections


INF = 10 ** 10


def solve(n, t, xs):
    trades = collections.Counter()
    maxs = [INF for _ in range(n)]
    maxs[n - 1] = xs[n - 1]
    for i in range(n - 1)[::-1]:
        maxs[i] = max(xs[i], maxs[i + 1])
    for i in range(n):
        delta = maxs[i] - xs[i]
        if delta > 0:
            trades[delta] += 1
    max_delta = max(trades.keys())
    return trades[max_delta]


def main():
    n, t = map(int, input().split())
    xs = list(map(int, input().split()))
    print(solve(n, t, xs))


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

N = int(input())
l = list(map(int,input().split()))
s = 0
for i in range(len(l)-1):
    for j in range(1,len(l)-i):
        s = s + l[i]*l[i+j]
s = s%(10**9+7)
print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = sum(A)
S2 = sum(map(lambda x:x**2,A))
 
print((S**2-S2)//2%(1000000000+7))
### BUGGY CODE ###

def pri_me(x):
    if x == 2:
        return True
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
#print(pri_me(n))


def prime_factorize(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 = int(input())
if n==1 or n == 0:
    print(0)
    exit()
if pri_me(n):
    print(1)
    exit()
N = n
ans = 0
for i in range(2,N+1):
    if n%i==0 and len(set(prime_factorize(i)))==1: 
        n=n//i
        ans += 1
    if n <=i:
        break
        #print(n,i)
        #print(len(set(prime_factorize(i)))
print(ans)


### FIXED CODE ###


def pri_me(x):
    if x == 2:
        return True
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
#print(pri_me(n))


def prime_factorize(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 = int(input())
if n==1 or n == 0:
    print(0)
    exit()
if pri_me(n):
    print(1)
    exit()
N = n
ans = 0
from collections import Counter
d=prime_factorize(n)
d = sorted(d)
for i in set(d):
    cnt = d.count(i)
    now = 1
    k = 1
    while now <=cnt:
        ans += 1
        k+=1
        now += k
print(ans)