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

def e(n):
    array = [1]*(n+1)
    k = 2
    while k*k <= n:
        if array[k] == 1:
            i = k
            while (i <= n/k):
                array[k*i] = 0
                i += 1
        k += 1
    prime = []
    i = 2
    while i <= n:
        if array[i] == 1:
            prime.append(i)
        i += 1
    return len(prime)
while True:
    try:
        n = int(input())
        print(e(n))
    except:
        break

### FIXED CODE ###

import sys
import math
M = 1000000
B = int(math.sqrt(M)+1)//6+1
N = M//6
N1 = N+1 if M % 6 == 5 else N
N2 = N+1 if M % 6 >= 1 else N
l = [1] * N1
m = [1] * N2
i = 5
ini = 4
for p in range(B):
    if l[p] == 1:
        l[p+i::i] = [0] * len(l[p+i::i])
        m[ini-1::i] = [0] * len(m[ini-1::i])
    if m[p] == 1:
        m[p+i+2::i+2] = [0] * len(m[p+i+2::i+2])
        l[ini+1::i+2] = [0] * len(l[ini+1::i+2])
    i += 6
    ini += 5
 
for i in sys.stdin:
    n = int(i)
    r =  n-1 if n < 3 else sum(l[0:(n+1)//6])+sum(m[0:(n-1)//6])+2
    print(r)
### BUGGY CODE ###

n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in [0]*n]
l.sort(key=lambda x:x[0])
ans = 0
tmpl = []
flag = True
i = 0
for d in range(1,m+1):
  while i<=n-1 and l[i][0] <= d:
    tmpl.append(l[i][1])
    i += 1
  if len(tmpl) > 0:
    maxindex = tmpl.index(max(tmpl))
    ans += tmpl[maxindex]
    del tmpl[maxindex]
print(ans)


### FIXED CODE ###

from heapq import heappush,heappop
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in [0]*n]
l.sort(key=lambda x:x[0])
ans = 0
tmpl = []
i = 0
for d in range(1,m+1):
  while i<=n-1 and l[i][0] <= d:
    #tmpl.append(l[i][1])
    heappush(tmpl,-l[i][1])
    i += 1
  if len(tmpl) > 0:
    #maxindex = tmpl.index(max(tmpl))
    #ans += tmpl[maxindex]
    #del tmpl[maxindex]
    ans -= heappop(tmpl)
print(ans)
### BUGGY CODE ###

A,B=map(int,input().split())
def cf(a,b):
  cf=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      cf.append(i)
  return cf
x=cf(A,B)
n=max(x)
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]]
ok=set(x)&set(primes(n))
print(len(ok)+1)

### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
s=set()
x=gcd(A,B)
y=2
while y*y<=x:
  while x%y==0:
    s.add(y)
    x//=y
  y+=1
if x>1:
  s.add(x)
print(len(s)+1)
### BUGGY CODE ###

import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))


##### Library ####



##### main #####
def main():
    input_S = input()
    K = I() - 1

    len_S = len(input_S)
    lis = []

    if len_S == 1:
        print(input_S)
    else:
        for i in range(len_S):
            for j in range(len_S):

                s = input_S[j:j+i+1]
                lis.append(s)
        print(sorted(set(lis))[K])

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))


##### Library ####


##### main #####
def main():

    input_S = input()
    K = I() - 1

    # input_S = 'abcaa'
    # K = 2

    len_S = len(input_S)
    unique_S = len(set(input_S))
    
    lis = set()
    min_s = 'z'

    if len_S == 1:
        print(input_S)

    else:
        for i in range(5):
            for j in range(len_S):
                if input_S[j] > min_s:
                    continue

                s = input_S[j:j+i+1]
                lis.add(s)

        print(sorted(lis)[K])

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

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n
tmp = 0

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid
print(high)
sys.stdout.flush()
s = input()
exit()

### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

N = int(input())
S = list(input())
cnt = 0

for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if 2*(j+1) - (i+1) - (k+1) != 0:
                if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                    cnt += 1
print(cnt)

### FIXED CODE ###

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

r , g, b = S.count("R"), S.count("G"), S.count("B")
ans = r * g * b

for i in range(N-2):
    for d in range(N//2+1):
        j = i + d
        k = j + d
        if k >= N:break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
kitaichi = []
for i in range(n):
    P = p[i]
    kitai = (((P*(P+1)/2))/P)
    kitaichi.append(kitai)
ans = []
for j in range((n-k)+1):
    a = sum(kitaichi[j:j+k])
    ans.append(a)
ans.sort(reverse=True)

print(ans[0])


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
kitaichi = []
for i in range(n):
    P = p[i]
    kitai = 1+P
    kitaichi.append(kitai)
m = [0,]
a = 0
for j in range(n):
    a += kitaichi[j]
    m.append(a)
ans = 0
for l in range(n-k+1):
    temp = m[l+k]-m[l]
    if temp> ans:
      ans = temp
print(ans/2)
### BUGGY CODE ###

from collections import Counter
from itertools import product
n=int(input())
s=str(input())
a=Counter(s)
aa=list(a.values())
aa.sort()
aa=aa[::-1]
m=len(aa)
ans=0
#print(aa)
for i in range(1,2**m):
    z=format(i,'b').zfill(m)
    #print(z)
    ans1=1
    for j in range(m):
        if int(z[j])>0:
            ans1*=aa[j]*int(z[j])%(10**9+7)
    ans+=ans1%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

from collections import Counter
n=int(input())
s=str(input())
a=Counter(s)
aa=list(a.values())
#print(aa)
ans=1
for i in aa:
    ans*=(i+1)%(10**9+7)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
toremove=set()
while(1):
    for j in range(len(ab)):
        if ab[0][1] > ab[j][0]:
            toremove.add(ab[j])
        else:break
    if len(toremove)>0:
        for r in toremove:
            ab.remove(r)
        toremove=set()
        res+=1
    if len(ab) == 0:break

print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
### BUGGY CODE ###

a,b,x = map(int,input().split())
ans = 0
for i in range(a,b+1):
    if i%x==0:
        ans += 1
print(ans)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a == 0:
    print(b//x + 1)
else:
    print((b//x) - ((a-1)//x))
### BUGGY CODE ###

from collections import defaultdict
from queue import Queue
n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
kenedge = defaultdict(set)
dist = [MX for i in range(n)]
reached = [False for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

for i in range(n):
    step1 = set()
    for ii in edge[i]:
        step1 |= edge[ii]
    step2 = set()
    for iii in step1:
        step2 |= edge[iii]
    step3 = set()
    for iiii in step2:
        kenedge[i].add(iiii)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s] = 0

q = Queue()
q.put(s)
while not q.empty():
    node = q.get()
    reached[node] = True
    for next_node in kenedge[node]:
        if not reached[next_node]: q.put(next_node)
        dist[next_node] = min(dist[next_node], dist[node] + 1)

if dist[t] == MX:
    print(-1)
else:
    print(dist[t])



### FIXED CODE ###

from collections import defaultdict
from queue import Queue

n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [[MX, MX, MX] for i in range(n)]
reached = [[False, False, False] for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s][0] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        reached[next_node][next_step] = True
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

if dist[t][0] == MX:
    print(-1)
else:
    print(dist[t][0])
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

d = [1 for _ in range(M)]
arr = np.array([list(map(int,input().split())) for _ in range(M)])
arr = arr.T - 1
graph = csr_matrix((d, (arr[0], arr[1])), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)

pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(10**6)

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for x in ls:
    counter = factorizations[x]
    s = 1
    for p, k in lcm.items():
        if p in counter:
            k -= counter[p]
        s *= pow(p, k, MOD)
    res += s
    res %= MOD
print(res)

### FIXED CODE ###

import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def gcd(a, b):
    while True:
        a, b = b, a % b
        if b == 0:
            break
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

x = ls[0]
for i in range(1, n):
    x = lcm(x, ls[i])
ds = [x // y for y in ls]
print(sum(ds) % MOD)
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        return sorted(a+b)[-m:]
        m = min(m, len(a) + len(b))
        res = [0] * m
        if len(a) == 0:
            return b
        if len(b) == 0:
            return a
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = merge(q, current, M - i)
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    # AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


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

from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for i in range (n)]

for i in range(1,n**2+1):
  ecnt=0
  seen=[0]*n
  ng=True
  for j in range(n):
    if not a[j]:
      ecnt+=1
      continue
    if seen[j]:
      continue
    seen[j]=1
    p=a[j][0]-1
    if seen[p]:
      continue
    if a[p][0]==j+1:
      ng=False
      a[p].popleft()
      a[j].popleft()
      seen[p]=1
  if ecnt==n:
      print(i-1)
      exit()
  if ng:
      print(-1)
      exit()

### FIXED CODE ###

from collections import deque
def tsort():
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    if len(l)!=P:
        print(-1)
        exit()
    return l
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
In=[0]*P
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
        In[A[i][j+1]]+=1
srted=tsort()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = set(map(int,input().split()))
    A = sorted(list(A))

    import bisect
    from operator import mul
    from functools import reduce

    def cmb(n,r):
        r = min(n-r,r)
        if r == 0: return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1,r + 1))
        return over // under
    
    ans=[0,0,0]

    for i in range(len(A)-1,-1,-1):
        x = A[i]
        y = A[i]//2

        tmp0=tmp1=tmp2=0

        if y in A:
            tmp0 = cmb(x,y)
        else:
            z = bisect.bisect_left(A,y,hi=max(0,i-1))
            tmp1 = cmb(x,A[z])
            tmp2 = cmb(x,A[max(0,z-1)])

        max_ = [[tmp0,x,y],[tmp1,x,A[z]],[tmp2,x,A[max(0,z-1)]]]
        max_ = sorted(max_,key=lambda x:x[0],reverse=True)

        if ans[0]<max_[0][0]:
            ans = max_[0]
        break
    print(ans[1],ans[2])

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = set(map(int,input().split()))
    A = sorted(list(A))

    import bisect

    ans = A[-1]/2
    b = bisect.bisect_left(A,ans)

    if abs(ans-A[b])<abs(ans-A[max(0,b-1)]):
        print(A[-1],A[b])
    else:
        print(A[-1],A[b-1])

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

class BinaryIndexedTree:
    def __init__(self, N, f=max, id=0):
        self.N = N
        self.bit = [id] * (self.N+1)
        self.f = f
        self.id = id

    def query(self, i):
        res = self.id
        while i > 0:
            res = self.f(res, self.bit[i])
            i -= i & -i
        return res

    def update(self, i, x):
        while i <= self.N:
            self.bit[i] = self.f(self.bit[i], x)
            i += i & -i

def main():
    N,*A=map(int, open(0).read().split())
    L,R=[0]*N,[0]*N
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A):
        L[a-1]=i-bit.query(a)
        bit.update(a, i)
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A[::-1]):
        R[a-1]=i-bit.query(a)
        bit.update(a, i)
    print(sum(L[i]*R[i]*(i+1) for i in range(N)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

class BinaryIndexedTree:
    def __init__(self, N, f=max, id=0):
        self.N = N
        self.bit = [id] * (self.N+1)
        self.f = f
        self.id = id

    def query(self, i):
        res = self.id
        while i > 0:
            res = self.f(res, self.bit[i])
            i -= i & -i
        return res

    def update(self, i, x):
        while i <= self.N:
            self.bit[i] = self.f(self.bit[i], x)
            i += i & -i

def main():
    N,*A=map(int, open(0).read().split())
    L,R=[0]*N,[0]*N
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A):
        L[a-1]=i-bit.query(a)
        bit.update(a, i)
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A[::-1]):
        R[a-1]=i-bit.query(a)
        bit.update(a, i)
    print(sum(L[i]*R[i]*(i+1) for i in range(N)))

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

def C_GreenBin():
    N = int(input())
    s = []
    for x in range(N):
        s.append(input())
    s_sort = []
    for x in range(N):
        s_sort.append(sorted(s[x]))
    result = 0
    for i in range(0, N - 1):
        for j in range(i + 1, N):
            if s_sort[i] == s_sort[j]:
                result += 1
    print(result)
    
if __name__ == "__main__":
    C_GreenBin()

### FIXED CODE ###

def C_GreenBin():
    from collections import Counter
    N = int(input())
    s = []
    for x in range(N):
        list_tmp = sorted(input())
        s.append("".join(list_tmp))
    result = 0
    s_tmp = Counter(s)
    for x in s_tmp.values():
        if x > 1:
            result += ((x - 1) * x) // 2
    print(result)
    
if __name__ == "__main__":
    C_GreenBin()
### BUGGY CODE ###

a, b, c, d= map(int, input().split())
ans = 0

a2 = d//a
b2 = d//b
c2 = d//c

for i in range(a2 + 1):
    for j in range(b2 + 1):
        for k in range(c2 + 1):
            sum = a * i + b * j + c * k
            if sum == d:
                ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range((N//R)+1):
    for g in range((N//G)+1):
        if r*R + g*G <= N and (N - r*R - g*G) % B == 0:
            ans += 1
print(ans)