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

#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    for i in range(1, N+1):
        for j in range(1, N+1):
            a[i][j] = a[i][j]+a[i][j-1]

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


class Bit:
    def __init__(self, n, m):
        self.size = [n, m]
        self.tree = [[0] * (n + 1) for _ in range(m+1)]

    def sum(self, i, j):
        s = 0
        while i > 0:
            jj = j
            while jj > 0:
                s += self.tree[i][jj]
                jj -= jj & -jj
            i -= i & -i
        return s

    def add(self, i, j, x):
        while i <= self.size[0]:
            jj = j
            while jj <= self.size[1]:
                self.tree[i][jj] += x
                jj += jj & -jj
            i += i & -i


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    b = Bit(N, N)

    for l, r in zip(L, R):
        b.add(N-l+1, r, 1)

    for pp, qq in zip(p, q):
        print(b.sum(N-pp+1, qq))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


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

n = int(input())
a = list(map(int,input().split()))
x = []
y = []
for i in range(n):
    if a[i] in x:
        y[x.index(a[i])] += 1
    else:
        x.append(a[i])
        y.append(1)
ans = 0
for i in range(len(y)):
    if y[i] >= 2:
        ans += y[i] * (y[i] - 1) // 2
for i in range(n):
    print(ans - (y[x.index(a[i])] - 1))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[a[i]] += 1
ans = 0
for i in range(len(b)):
    ans += b[i] * (b[i]-1) // 2
for i in range(n):
    print(ans - (b[a[i]] - 1))
### BUGGY CODE ###

H, W = map(int, input().split())
F = [input() for _ in range(H)]


def search(x, y):
    if not (0 <= x < H and 0 <= y < W):
        return False
    if F[x][y] == "#":
        return False
    else:
        return True


ans = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == ".":
            count = 1
            x, y = i, j
            while True:
                if search(x, y+1):
                    count += 1
                    y += 1
                else:
                    break
            x, y = i, j
            while True:
                if search(x+1, y):
                    count += 1
                    x += 1
                else:
                    break
            x, y = i, j
            while True:
                if search(x-1, y):
                    count += 1
                    x -= 1
                else:
                    break
            x, y = i, j
            while True:
                if search(x, y-1):
                    count += 1
                    y -= 1
                else:
                    break
            if count > ans:
                ans = count

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
F = np.array([[1 if i == "." else 0 for i in input()] for _ in range(H)])
FU = np.zeros((H, W), dtype=int)
FD = np.zeros((H+1, W), dtype=int)
FL = np.zeros((H, W), dtype=int)
FR = np.zeros((H, W+1), dtype=int)

for i in range(H):
    FU[i] += (FU[i-1]+1)*F[i]

for i in range(H-1, -1, -1):
    FD[i] += (FD[i+1]+1)*F[i]

for i in range(W):
    FL[:, i] += (FL[:, i-1]+1)*F[:, i]

for i in range(W-1, -1, -1):
    FR[:, i] += (FR[:, i+1]+1)*F[:, i]

FV = FU + FD[:-1] - 1
FH = FL + FR[:, :-1] - 1
ans = np.max(FV+FH)
if ans >= 2:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    h = [0]*N
    for i in range(N):
        h[i] = int(input())
    hh = sorted(h)

    ans = 10**10
    for i in range(N-K+1):
        ans = min(ans, max(hh[i:i+K])-min(hh[i:i+K]))
    print(ans)
    
main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = [0]*N
    for i in range(N):
        h[i] = int(input())
    h.sort()
    
    ans = 10**10
    for i in range(N-K+1):
        ans = min(ans, h[i+K-1]-h[i])
    print(ans)
main()
### BUGGY CODE ###

N, Y = map(int, input().split())
exit = False

for i in range(2500):
    if 10000 * i > Y or exit == True:
        break
    for j in range(5000):
        if 10000*i + 5000*j > Y or exit == True:
            break
        for k in range(25000):
                if 10000*i + 5000*j + 1000*k > Y or exit == True:
                    break
                if 10000*i + 5000*j + 1000*k == Y and i + j + k == N:
                    print("{} {} {}".format(i, j, k))
                    exit = True

if exit == False:
    print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split())
exit = False

for i in range(N+1):
    if exit == True:
        break
    for j in range(N-i+1):
        if exit == True:
            break
        k = N - i - j
        if 10000*i + 5000*j + 1000*k == Y:
            exit = True
            print("{} {} {}".format(i, j, k))
            
if exit == False:
    print("-1 -1 -1")
### BUGGY CODE ###

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

import numpy as np
exps = np.array(p) / 2 + 0.5

m = 0
for i in range(0, n - k + 1):
    tmp = exps[i:i + k].sum()
    if tmp > m:
        m = tmp
print(m)

### FIXED CODE ###

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

import numpy as np
exps = np.array(p) / 2 + 0.5

s = exps[:k].sum()
m = s
for i in range(1, n - k + 1):
    s = s - exps[i-1] + exps[i+k-1]
    if s > m:
        m = s
print(m)
### BUGGY CODE ###

import numpy as np

N = int(input())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = np.array([[0]*3]*N)
dp[0][0],dp[0][1],dp[0][2] = abc[0][0],abc[0][1],abc[0][2]

for i in range(1,N):
  for j in range(3):
    for k in range(3):
      if j != k:
        dp[i][k] = max(dp[i][k], dp[i-1][j] + abc[i][k])

ans = 0

for l in range(N):
  ans = max(ans, max(dp[l]))
print(ans)

### FIXED CODE ###

N = int(input())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0][0],dp[0][1],dp[0][2] = abc[0][0],abc[0][1],abc[0][2]

for i in range(1,N):
  for j in range(3):
    for k in range(3):
      if j != k:
        dp[i][k] = max(dp[i][k], dp[i-1][j] + abc[i][k])

ans = max(dp[N-1])
print(ans)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))

cnt = 0
for i in range(1, N+1) :
   
    m = min(P[:i])

    if P[i-1] == m :
        cnt = cnt + 1

print(cnt)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

cnt = 0
pre_m = P[0]
for i in range(1, N+1) :
   
    m = min(P[i-1:i])
    if pre_m > m :
        pre_m = m
    else :
        m = pre_m

    if P[i-1] == m :
        cnt = cnt + 1

print(cnt)
### BUGGY CODE ###

s = input()
a = int(s)%2019
mod_N = [0]*2019
mod_N[a%2019] += 1
for i in range(len(s)):
  a = (a-int(s[i])*10**(len(s)-i-1))%2019
  mod_N[a] += 1
ans = 0
for i in mod_N:
  ans += i*(i-1)//2
print(ans)


### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

n=int(input())
ans=0
l=[]
for i in range(n):
  a=int(input())
  if a in l:
    ans-=1
    l.remove(a)
  else:
    l.append(a)
    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
l=[int(input()) for i in range(n)]
from collections import Counter
lst=list(Counter(l).values())
def mod2(n):
  if n%2==1:
    return 1
  else:
    return 0
ans=0
for i in lst:
  ans+=mod2(i)
print(ans)
### BUGGY CODE ###

N = 1000000
X = [-1] * (N+1)
L = [{} for _ in range(N+1)]
k = 2
while k <= N:
    X[k] = 1
    L[k][k] = 1
    for i in range(k*2, N+1, k):
        X[i] = 0
        L[i][k] = 1
    d = 2
    while k**d <= N:
        for i in range(k**d, N+1, k**d):
            L[i][k] += 1
        d += 1
    while k <= N and X[k] >= 0:
        k += 1
P = [i for i in range(N+1) if X[i] == 1]


### FIXED CODE ###

P = 998244353
N = int(input())
A = [int(a) for a in input().split()]
V = max(A) + 1
X = [0] * V
for a in A:
    X[a] += 1

fa = [1]
for i in range(1, V):
    fa.append(fa[-1]*i%P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, V)[::-1]:
    fainv.append(fainv[-1]*i%P)
fainv = fainv[::-1]
W = [1] + [fainv[i] * fa[i-1] % P for i in range(1, V)]

for k in range(1, V):
    for i in range(k*2, V, k):
        W[i] = (W[i] - W[k]) % P

ans = 0
for k in range(1, V):
    s1 = 0
    s2 = 0
    for i in range(k, V, k):
        if X[i]:
            s1 += i * X[i]
            s2 += i * i * X[i]
    ans = (ans + (s1*s1-s2) * W[k]) % P
print(ans * fainv[2] % P)
### BUGGY CODE ###

from math import gcd
K = int(input())
ans = 0

for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1),k+1)
print(ans)        

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0

for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1),k+1)
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
list = list(map(int, input().split(' ')))

result = []
for v in itertools.permutations(list, N):
    avg = 0
    for num in v:
        if avg == 0:
            avg = num
        else:
            avg = (num + avg) / 2
    result.append(avg)

print(max(result))


### FIXED CODE ###

N = int(input())
list = list(map(int, input().split(' ')))

list.sort()
avg = 0
for num in list:
    if avg == 0:
        avg = num
    else:
        avg = (num + avg) / 2
print(avg)
### BUGGY CODE ###

R, G, B, N = map(int,input().split())
count = 0
i_range = N//R+1
j_range = N//G+1

for i in range (i_range):
    for j in range (j_range):
        if (N - i*R - j*G)%B == 0 and (N - i*R - j*G)>=0:
            count += 1
print(count)


### FIXED CODE ###

R, G, B, N = map(int,input().split())
count = 0
i_range = N//R+1
j_range = N//G+1

for i in range (N//R+1):
    for j in range (N//G+1):
        if (N - i*R - j*G)%B == 0 and (N - i*R - j*G)>=0:
            count += 1
print(count)
### BUGGY CODE ###

def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  import collections

  if p == 2 or p == 5:
      for i in range(n):
          if int(s[i]) % p == 0:
              ans += i + 1
      print(ans)
      exit()

  else:
    chk = []
    m = 0
    chk = collections.deque(chk)
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i)+m)%p
      chk.append(m)
    chk.append(0)
    chk = list(chk)
    c = collections.Counter(chk)
    for i in range(p):
      ans += c[i]*(c[i]-1)/2
    print(int(ans))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

import math
def nCr(n, r):
  if n < r:
    return 0
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += nCr(i,2)
  print(ans)
### BUGGY CODE ###

def resolve():
    A, B, K = map(int, input().split())
    count = []
    ans = []
    for _ in range(B-A+1):
        count.append(A+_)
    if K > B-A-1:
        K = B-A+1
    for i in range(K):
        ans.append(count[i])
        ans.append(count[(i+1)*-1])
    an = sorted(set(ans))
    for i in range(len(an)):
        print(an[i])
resolve()

### FIXED CODE ###

def resolve():
    A, B, K = map(int, input().split())
    if 2*K > B-A+1:
        for _ in range(B-A+1):
            print(A+_)
    else:
        for i in range(K):
            print(A+i)
        for j in range(K):
            print(B-K+j+1)
resolve()
### BUGGY CODE ###

import heapq as h

N,M=map(int,input().split())
to=[[] for i in range(0,N)]
fr=[[] for i in range(0,N)]
for i in range(0,N+M-1):
    a,b=map(int,input().split())
    to[a-1].append(b-1)
    fr[b-1].append(a-1)

root=-1
for i in range(0,N):
    if fr[i]==[]:
        root=i
        break


parent=[-1 for i in range(0,N)]
q=[]
q.append(root)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in to[x]:
            h.heappush(sub,p)
            parent[p]=x
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

for i in range(0,N):
    print(parent[i]+1)

### FIXED CODE ###

import heapq as h
import sys

input=sys.stdin.readline


N,M=map(int,input().split())
to=[set([]) for i in range(0,N)]
fr=[set([]) for i in range(0,N)]
for i in range(0,N+M-1):
    a,b=map(int,input().split())
    to[a-1].add(b-1)
    fr[b-1].add(a-1)

root=-1
for i in range(0,N):
    if fr[i]==set([]):
        root=i
        break

parent=[-1 for i in range(0,N)]
visited=set([])
q=[]
q.append(root)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        visited.add(x)
        for p in to[x]:
            if visited>=fr[p]:
                h.heappush(sub,p)
                parent[p]=x
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

for i in range(0,N):
    print(parent[i]+1)
### BUGGY CODE ###

import math
import sys
import bisect

sys.setrecursionlimit(10**8)

N = int(input())
A = list(map(int,input().split()))
Asum = [0]
aa = 0

#Asum[i] = A[0]+A[1]+ … +A[i-1]
for i in range(N):
	aa += A[i]
	Asum.append(aa)


ans = 10**20
	
	
for c in range(2,N-1):
	AL = A[:c]
	AR = A[c:]
	
	AsumL = Asum[c]
	AsumR = Asum[-1] - AsumL
	
	Lh = AsumL/2
	Rh = AsumR/2
		
	Lh_i = bisect.bisect_left(Asum,Lh)
	L1 = abs(Asum[Lh_i] - Lh)
	L2 = abs(Asum[Lh_i-1] - Lh)
	if L1 <= L2:
		B = Asum[Lh_i]
	else:
		B = Asum[Lh_i-1]
	
	C = AsumL - B

	Rh_i = bisect.bisect_left(Asum,Rh+AsumL)
	R1 = abs(Asum[Rh_i] - AsumL - Rh)
	R2 = abs(Asum[Rh_i-1] - AsumL - Rh)
	if R1 <= R2:
		D = Asum[Rh_i] - AsumL
	else:
		D = Asum[Rh_i-1] - AsumL
	
	E = AsumR - D
	
	dist = max(B,C,D,E) - min(B,C,D,E)	
	ans = min(ans,dist)
	
print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

N = int(input())
aa = inpl()
SUM = sum(aa)
SUMaa_L = [0]
SUMaa_R = [SUM]

tmp = 0
for a in aa:
	tmp += a
	SUMaa_L.append(tmp)
	SUMaa_R.append(SUM-tmp)

cutL = []
l = 1
SUML = SUMaa_L[l]
for cutM in range(2,N-1):
	SUM = SUMaa_L[cutM]
	while SUML < SUM/2:
		l += 1
		SUML = SUMaa_L[l]
	l1,l2 = SUMaa_L[l-1], SUMaa_L[l]
	r1,r2 = SUM-l1, SUM-l2
	if abs(l1-r1) > abs(l2-r2):
		cutL.append([l2,r2])
	else:
		cutL.append([l1,r1])

cutR = []
r = N-1
SUMR = SUMaa_R[r]
for cutM in reversed(range(2,N-1)):
	SUM = SUMaa_R[cutM]
	while SUMR < SUM/2:
		r -= 1
		SUMR = SUMaa_R[r]
	l1,l2 = SUMaa_R[r+1], SUMaa_R[r]
	r1,r2 = SUM-l1, SUM-l2
	if abs(l1-r1) > abs(l2-r2):
		cutR.append([l2,r2])
	else:
		cutR.append([l1,r1])

ans = INF
for i in range(N-3):
	a,b = cutL[i]
	c,d = cutR[N-4-i]
	ans = min(ans,max(a,b,c,d)-min(a,b,c,d))

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

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

if K == 1:
  res = 0
elif K == 2:
  res = K % 2
else:
  diff = abs(N-K)
  while diff < N:
    N  = diff
    diff = abs(N-K)
 
  res = N
  
  
print(res)
  

### FIXED CODE ###

N, K = map(int, input().split())
rem = N %K
print(min(rem, abs(rem - K)))
### BUGGY CODE ###

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

A = sorted([a for a in A if a < K])
N = len(A)

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m+1:]

    if sum(B) < K-A[m]:
        l = m
        continue

    dp = [False] * (K+1)
    dp[0] = True
    for i in range(N-1):
        for j in range(K+1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j-B[i]]

    for k in range(K-A[m], K+1):
        if dp[k]:
            if k >= K:  # 不要
                l = m
            else:
                r = m
            break
    else:
        l = m

print(r)


### FIXED CODE ###

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)
### BUGGY CODE ###

import collections
n, k = map(int, raw_input().split())
num = map(int, raw_input().split())
n = int()
num = collections.Counter(num)
while True:
    if len(num) <= k:
        print n
        break
    t, v = sorted(num.items(), key=lambda x:x[1])[0]
    del num[t]
    n += v


### FIXED CODE ###

import collections
n, k = map(int, raw_input().split())
num = map(int, raw_input().split())
n = int()
num = collections.Counter(num)
for t, v in sorted(num.items(), key=lambda x:x[1])[0:-k]:
    n += v
print n
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=1
for i in A:
    ans = ans*i
if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

def cal():
    N=int(input())
    A=list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    ans=1
    for i in A:
        ans = i*ans
        if ans > 1000000000000000000:
            print(-1)
            return
    print(ans)

cal()
### BUGGY CODE ###

import math
from collections import defaultdict
from itertools import product
from functools import reduce 
from operator import mul


def is_prime(num):
    if not isinstance(num, int):
        return False
    if num <= 1:
        return False
    if num == 2 or num == 3:
        return True
    if num % 6 in [0, 2, 3, 4]:
        return False
    div_max = int(math.sqrt(num))
    for div in range(5, div_max + 1, 2):
        if num % div == 0:
            return False
    return True

def factorint(x):
    factors = defaultdict(int)
    while not is_prime(x):
        div_max = int(math.sqrt(x))
        for div in range(2, div_max + 1):
            if x % div == 0:
                factors[div] += 1
                x = int(x / div)
                break
    factors[x] += 1
    return factors

ans = 0
n = int(input())
if n==0:
    print(0)
    exit()
rn = math.sqrt(n+1) + 1
factor_dict = factorint(n)
ks = [range(k+1) for k in factor_dict.values()]
prs = product(*ks)
for pr in prs:
    s = reduce(mul, [factor**p for factor,p in zip(factor_dict.keys(), pr)])
    if s >= rn:
        ans += s -1
print(ans)


### FIXED CODE ###

import math
from collections import defaultdict
from itertools import product
from functools import reduce 
from operator import mul


def is_prime(num):
    if not isinstance(num, int):
        return False
    if num <= 1:
        return False
    if num == 2 or num == 3:
        return True
    if num % 6 in [0, 2, 3, 4]:
        return False
    div_max = int(math.sqrt(num))
    for div in range(5, div_max + 1, 2):
        if num % div == 0:
            return False
    return True

def factorint(x):
    factors = defaultdict(int)
    if x==1:
        factors[1] = 1
        return factors
    while not is_prime(x):
        div_max = int(math.sqrt(x))
        for div in range(2, div_max + 1):
            if x % div == 0:
                factors[div] += 1
                x = int(x / div)
                break
    factors[x] += 1
    return factors

ans = 0
n = int(input())
rn = math.sqrt(n+1) + 1
factor_dict = factorint(n)
ks = [range(k+1) for k in factor_dict.values()]
prs = product(*ks)
for pr in prs:
    s = reduce(mul, [factor**p for factor,p in zip(factor_dict.keys(), pr)])
    if s >= rn:
        ans += s -1
print(ans)
### BUGGY CODE ###

n = int(input())
s_li = []
for i in range(n):
    s = input()
    s_i = {}
    for j in range(10):
        s_i[s[j]] = 0
    for j in range(10):
        s_i[s[j]] += 1
    buf = ""
    for k, v in sorted(s_i.items()):
        buf += str(k) + str(v)
    s_li.append(buf)

ans = 0

for i in range(n):
    for j in range(n):
        if i >= j :
            continue
        if s_li[i] == s_li[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s_li = [input() for i in range(n)]

ans = 0
s_dict = {}
for i in s_li :
    s_i = [ch for ch in i]
    s_i.sort()
    s_i = "".join(s_i)
    if s_i in s_dict :
        ans += s_dict[s_i]
        s_dict[s_i] += 1
    else :
        s_dict[s_i] = 1
print(ans)
### BUGGY CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
R,G,B,N = inputlist()
ans = 0
for r in range(N//R + 1):
    for g in range(N//G + 1):
        b = N -(r*R+g*G)
        if b < 0:
            continue
        if b % B == 0:
            ans +=1
print(ans)

### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
R,G,B,N = inputlist()
ans = 0
for r in range(N//R + 1):
    for g in range(N//G + 1):
        b = N -(r*R+g*G)
        if b < 0:
            continue
        if b % B == 0:
            ans +=1
print(ans)