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

import itertools

int1 = lambda x: int(x) - 1

H, W, N = map(int, input().split())
B = set(tuple(map(int1, input().split())) for _ in range(N))

adj = (-1, 0, 1)
visited = set()
ans = [0] * 10
for a, b in B:
    for dy, dx in itertools.product(adj, repeat=2):
        if not (1 <= a + dy < H - 1 and 1 <= b + dx < W - 1):
            continue
        elif (a + dy, b + dx) in visited:
            continue
        visited.add((a + dy, b + dx))
        c = 0
        for ddy, ddx in itertools.product(adj, repeat=2):
            if (a + dy + ddy, b + dx + ddx) in B:
                c += 1
        ans[c] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
for x in ans:
    print(x)


### FIXED CODE ###

import itertools

int1 = lambda x: int(x) - 1

H, W, N = map(int, input().split())
B = set(tuple(map(int1, input().split())) for _ in range(N))

adj = (-1, 0, 1)
visited = set()
ans = [0] * 10
for a, b in B:
    for dy, dx in itertools.product(adj, repeat=2):
        if not (1 <= a + dy < H - 1 and 1 <= b + dx < W - 1):
            continue
        elif (a + dy, b + dx) in visited:
            continue
        visited.add((a + dy, b + dx))
        c = 0
        for ddy, ddx in itertools.product(adj, repeat=2):
            if (a + dy + ddy, b + dx + ddx) in B:
                c += 1
        ans[c] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
for x in ans:
    print(x)
### BUGGY CODE ###

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

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

for i in range(M):
    B, C = list(map(int,input().split()))
    A += [C]*B

A.sort()
A.reverse()

print(sum(A[:N]))

### FIXED CODE ###

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

A = [-1]
A += list(map(int,input().split()))
A.sort()

BC = [[1,-1]]

for i in range(M):
    BC.append(list(map(int,input().split())))

BC = sorted(BC, key=lambda x: x[1])


x = 0

for i in range(N):
    if A[-1] > BC[-1][1]:
        x += A.pop()
        
    else:
        x += BC[-1][1]
        BC[-1][0] -= 1
        if BC[-1][0] == 0:
            BC.pop()

print(x)
### BUGGY CODE ###

N,K=map(int,input().split())
mod=7+10**9
ans=0
l=range(0,N+1)
for i in range(K,N+2):
    ans+=(sum(l[-(i%(N+1)):])-sum(l[:i])+1)
print(ans%mod)



### FIXED CODE ###

N,K=map(int,input().split())
mod=7+10**9
ans=0
l=list(range(0,N+1))
for i in range(1,N+1):
    l[i]+=l[i-1]
for i in range(K,N+2):
    ans+=(l[-1]-l[-((1+i)%(N+2))]-l[i-1]+1)%mod
print(ans%mod)
### BUGGY CODE ###

n= int(input())
s= input()

snum = tuple(s[:])

ret =0
for i in range(1,n-1):
    for j in range(i,n):
        if snum[i-1] == snum[j-1]:
            continue
        eq_flg=False
        # j_i = j-i
        skip_k = j*2-i
        for k in range(j,n+1):
            if eq_flg == False:
                # if j_i == k-j:
                if k == skip_k:
                    eq_flg = True
                    continue
            if snum[i-1] == snum[k-1] or snum[j-1] == snum[k-1]:
                continue
            ret += 1

print(ret)


### FIXED CODE ###

def main():
    n= int(input())
    s= input()

    r = s.count("R")
    g = s.count("G")
    b = s.count("B")

    ans = r * g * b
    snum = tuple(s[:])
    for i in range(1,n-1):
        for j in range(i,n):
            k = j * 2 - i
            if k > n:
                break

            if snum[i-1] != snum[j-1] and snum[i-1] != snum[k-1] and snum[j-1] != snum[k-1]:
                ans -= 1

    print(ans)


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

N, Q = map(int,input().split())
S = input()



memo = {}
def init_memo():
    for start in range(N):
        for end in range(start,N):
            if start == end == 0:
                memo[(start,end)] = 0
            elif start == end:
                memo[(start,end)] = memo[(start-1,end)] - int(S[start-1:start+1]=="AC")
            else:
                memo[(start, end)] = memo[(start,end-1)] + int(S[end-1:end+1] == "AC")

init_memo()

for _ in range(Q):
    l, r = map(int,input().split())
    print(memo[(l-1,r-1)])

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
memo = [0 for _ in [0]*(N+1)]
for i in range(2,N+1):
    memo[i] = memo[i-1] + int(S[i-2:i]=="AC")
for _ in range(Q):
    l, r = map(int,input().split())
    print(memo[r]-memo[l])
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = input()
for i in range(10):
	c = str(i)
	if c.count(s) >= 4:
		s = s.replace(c, "")
		s = s + c*3
a = list(combinations(list(s),3))
b = set(a)
print (len(b))

### FIXED CODE ###

n = int(input())
s = input()

a = ["0","1","2","3","4","5","6","7","8","9"]

c = 0

for i in a:
	for j in a:
		for k in a:
			d = s.find(i)
			if d == -1:
				continue
			e = s[d+1:].find(j)
			if e == -1:
				continue
			e += d+1
			f = s[e+1:].find(k)
			if f == -1:
				continue
			c += 1
print (c)
### BUGGY CODE ###

N = int(input())
p = list(map(int,input().split()))
cou = 0

for i in range(N):
    num = min(p[0:i+1])
    if p[i] == num:
        cou += 1
    
print(cou)
    

### FIXED CODE ###

#41
import math
N = int(input())
p = list(map(int,input().split()))

cou = 0
x = math.inf

for j in range(N):
    if min(x,p[j]) == p[j]:
        x = p[j]
        cou += 1

print(cou)
### BUGGY CODE ###

n,m = map(int,input().split())
mod = 1000000007
x = list(map(int,input().split()))
y = list(map(int,input().split()))
ya = [0] * (m-1)
for i in range(m-1):
  ya[i] = y[i+1] - y[i]
ans = 0
for i in range(n-1):
  for j in range(m-1):
    ans += (x[i+1] - x[i]) * ya[j] *(i+1)*(j+1)*(n-i-1)*(m-j-1)
    ans = ans%mod
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
mod = 1000000007
x = list(map(int,input().split()))
y = list(map(int,input().split()))
xa = 0
ya = 0
for i in range(m):
  ya += (i)*y[i] -(m-i-1) *y[i]
for i in range(n):
  xa += (i)*x[i] -(n-i-1) *x[i]
print(ya*xa%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += a[i]*a[j]
ans %= mod
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0
aa=sum(a)
for i in range(n):
    aa-=a[i]
    ans += a[i]*aa
ans %= mod
print(ans)
### BUGGY CODE ###

N=int(input())

a=0
while N>=1:
    a+=N%10
    N=N//10

if a%9==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=input()



a=0
for i in range(len(N)):
    a+=int(N[i])

if a%9==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
num = list(map(int,input().split()))
m = 10**9 + 7
ans = 0

for i in range(n):
  sum_i = num[i] * (sum(num[i+1:n]) % m)
  ans += sum_i

print(ans%m)

### FIXED CODE ###

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

s1 = (sum(nums) - nums[0]) % (10**9 + 7)
sums = [s1]
for i in range(1,n):
  s = sums[i-1] - nums[i]
  s %= 10**9 + 7
  sums.append(s)

ans = 0
for i in range(n):
  temp = nums[i] * sums[i] % (10**9 + 7)
  ans += temp

print(ans%(10**9+7))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[-1]+A
still=[1]
before=1
rS=-1
root=[1]
while True:
  dest=A[before]
  if dest in still:
    rS=dest
    break
  else:
    still.append(dest)
    root.append(dest)
    before=dest
#print(root,rS)
num=0
for i in root:
  if i==rS:
    break
  num+=1
#print(num)
if K<=num:
  print(root[K])
else:
  K-=num
  root2=root[num:]
  print(root2[K%len(root2)])
  

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[-1]+A
still=[0]*(N+1)
still[1]=1
before=1
rS=-1
root=[1]
while True:
  dest=A[before]
  if still[dest]==1:
    rS=dest
    break
  else:
    still[dest]=1
    root.append(dest)
    before=dest
#print(root,rS)
num=0
for i in root:
  if i==rS:
    break
  num+=1
#print(num)
if K<=num:
  print(root[K])
else:
  K-=num
  root2=root[num:]
  print(root2[K%len(root2)])
### BUGGY CODE ###

import numpy as np

h,w=map(int,input().split())
s=[input() for i in range(h)]

l=[[0 for i in range(w)] for j in range(h)]
r=[[0 for i in range(w)] for j in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
u=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            if j == 0:
                l[i][j]=1
            else:
                l[i][j]=l[i][j-1]+1

for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j]==".":
            if j == w-1:
                r[i][j]=1
            else:
                r[i][j]=r[i][j+1]+1

for j in range(w):
    for i in range(h-1,-1,-1):
        if s[i][j]==".":
            if i == h-1:
                d[i][j]=1
            else:
                d[i][j]=d[i+1][j]+1

for j in range(w):
    for i in range(h):
        if s[i][j]==".":
            if i == 0:
                u[i][j]=1
            else:
                u[i][j]=u[i-1][j]+1

ans=0
x=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        x[i][j] = l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
        ans=max(ans,max(x[i]))

print(ans)

### FIXED CODE ###

import numpy as np

h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))
grid=(np.array(s) ==".") *1

l=np.zeros((h,w),dtype=int)
r=np.zeros((h,w),dtype=int)
u=np.zeros((h,w),dtype=int)
d=np.zeros((h,w),dtype=int)

for j in range(w):
    if j == 0:
        l[:,j] = grid[:,j]
    else:
        l[:,j] = (l[:,j-1]+1) * grid[:,j]
for j in range(w-1,-1,-1):
    if j == (w-1):
        r[:,j] = grid[:,j]
    else:
        r[:,j] = (r[:,j+1] +1)*grid[:,j]

for i in range(h):
    if i == 0:
        u[i,:]=grid[i,:]
    else:
        u[i,:]=(u[i-1,:]+1)*grid[i,:]
for i in range(h-1,-1,-1):
    if i==(h-1):
        d[i,:]=grid[i,:]
    else:
        d[i,:]=(d[i+1,:]+1)*grid[i,:]


ans=np.max(l+r+u+d-3)
print(ans)
### BUGGY CODE ###

l,r = map(int,input().split())

min = 99999999
for i in range(l,r):
  for j in range(i+1,r+1):
    value = (i*j)%2019
    if min > value:
      min = value
print(min)

### FIXED CODE ###

l,r = map(int,input().split())

r = min(r, l+4038)

min = 99999999
for i in range(l,r):
  for j in range(i+1,r+1):
    value = (i*j)%2019
    if min > value:
      min = value
print(min)
### BUGGY CODE ###

X = int(input())
time = 0
while True:
    if sum(range(time+1)) >= X:
        break
    time+=1
print(time)

### FIXED CODE ###

X = int(input())
for i in range(X+1):
    if (i*(i+1)/2) >= X:
        time = i
        break
print(time)
### BUGGY CODE ###

N,K=map(int,input().split())
def dfs(level,req,seq):
  if len(seq)==req:
    return
  if level==0:
    seq.append("P")
    return
  elif level>=1:
    seq.append("B")
    level-=1
    dfs(level,req,seq)
    seq.append("P")
    dfs(level,req,seq)
    seq.append("B")
    return seq
seq=[] 
if N==K==1:
  print("0")
else:
  seq=dfs(N,K,seq)
  #ans=seq[:K]
  ans=[i for i in seq if i=='P']
  print(len(ans))
  
  



### FIXED CODE ###

N,K=map(int,input().split())
a=[1]
p=[1]
for i in range(N):
  a.append(a[i]*2+3)
  p.append(p[i]*2+1)
def find(N,K):
  if N==0:
    return 0 if K<=0 else 1
  elif K<=a[N-1]+1:
    return find(N-1,K-1)
  else:
    return p[N-1]+1+find(N-1,K-2-a[N-1])
print(find(N,K))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
l_i = [a[i] + i + 1 for i in range(len(a))]
l_j = [i - a[i] + 1 for i in range(len(a))]

ans = 0
for i in range(n):
    for j in range(i+1, n):
        if l_i[i] == l_j[j]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
l_i = [a[i] + i + 1 for i in range(len(a))]
r_j = [i - a[i] + 1 for i in range(len(a))]
dl = defaultdict(int)
dr = defaultdict(int)
for i in range(n):
    dl[l_i[i]] += 1
    dr[r_j[i]] += 1

ans = 0
for i in dl.keys():
    ans += dl[i] * dr[i]

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

li=[]
a,b,n=map(int,input().split())
for x in range(1,n+1):
    li.append((a*x)//b-a*(x//b))
print(max(li))

### FIXED CODE ###

a,b,n=map(int,input().split())
print((a*min(n,b-1))//b)
### BUGGY CODE ###

import sys
N = int(input())
S = input()

ans = 0
while True:
    ans += S.count("#.")
    S = S.replace("#.", "")
    if S == S.replace("#.", ""):
        print(ans)
        break


### FIXED CODE ###

N = int(input())
s = input()

b_cnt, w_cnt = [0], [0]
for si in s:
    if si==".":
        b_cnt.append(b_cnt[-1])
        w_cnt.append(w_cnt[-1]+1)
    else:
        b_cnt.append(b_cnt[-1]+1)
        w_cnt.append(w_cnt[-1])

b_cnt = b_cnt[1:]
w_cnt = w_cnt[1:]
# print(b_cnt)
# print(w_cnt)
w = s.count(".")
b = s.count("#")
ans = float('inf')
ans = min(w, b)
for i in range(N):
    cond = b_cnt[i] + w - w_cnt[i]
    ans = min(ans, cond)

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

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np

N, X, Y = map(int, input().split())
F = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    F[i][i + 1] = 1
    F[i + 1][i] = 1
F[X - 1][Y - 1] = 1
F[Y - 1][X - 1] = 1

G = csgraph_from_dense(F, null_value=0)
d = dijkstra(G)

# print(F)
# print(d)

# print(np.count_nonzero(d == 1))
for i in range(1, N):
    print(np.count_nonzero(d == i) // 2)


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
from collections import Counter

N, X, Y = map(int, input().split())
F = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    F[i][i + 1] = 1
    F[i + 1][i] = 1
F[X - 1][Y - 1] = 1
F[Y - 1][X - 1] = 1

G = csgraph_from_dense(F, null_value=0)
d = dijkstra(G)

# print(F)
# print(d)

# print(np.count_nonzero(d == 1))
s = Counter(d.flatten().astype(np.int64))
# print(s)
for i in range(1, N):
    if i in s:
        print(s[i] // 2)
    else:
        print(0)
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 1: 
        print(1)
        return 0

    B = [False] * (max(A) + 1)
    nums = dict()
    for a in A:
        B[a] = True
        if a in nums: nums[a] += 1
        else: nums[a] = 1
    
    ans = 0
    for k in nums:
        if nums[k] > 1: continue
        else:
            flag = True
            for i in range(1, k):
                if i ** 2 > k: break
                if k % i == 0:
                    if B[i]:
                        flag = False
                        break
                    if B[k // i] and k // i < k:
                        flag = False
                        break
            if flag: ans += 1
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort()
    L = max(A)
    ad = defaultdict(int)
    for a in A: ad[a] += 1

    ans = 0
    B = [True] * (L + 1)
    for a in A:
        if B[a]:
            if ad[a] == 1: ans += 1
        k = 2 * a
        while k <= L:
            B[k] = False
            k += a

    print(ans)

    return 0

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

import math
import collections
n=int(input())
s=[sorted(input()) for _ in range(n)]
c=[str(collections.Counter(s[i])) for i in range(n)]
k=collections.Counter(c).values()
ans = 0
for i in k:
	if i >= 2:
		ans += math.factorial(i)//2//math.factorial(i-2)
print(ans)

### FIXED CODE ###

import math
import collections
n=int(input())
s=[sorted(input()) for _ in range(n)]
c=[str(collections.Counter(s[i])) for i in range(n)]
k=collections.Counter(c).values()
ans = 0
for i in k:
	if i >= 2:
		ans += math.factorial(i)//2//math.factorial(i-2)
print(ans)
### BUGGY CODE ###

import heapq
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b,c = map(int,input().split())
    edge[a-1].append([c,b-1])
    edge[b-1].append([c,a-1])

dist = []
for i in range(N):
    dist.append(dijkstra_heap(i,edge))

Q,K = map(int,input().split())
for i in range(Q):
    x,y = map(int,input().split())
    print(int(dist[x-1][K-1]+dist[K-1][y-1]))

### FIXED CODE ###

import heapq

"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b,c = map(int,input().split())
    edge[a-1].append([c,b-1])
    edge[b-1].append([c,a-1])


Q,K = map(int,input().split())
dist = dijkstra_heap(K-1,edge)
 
for i in range(Q):
    x,y = map(int,input().split())
    print(int(dist[x-1]+dist[y-1]))
### BUGGY CODE ###

N, K = map(int, input().split())
tmp = input().split(' ')
A = []
for i in range(N):
    A = A + [int(tmp[i])]

while K > 0 and A.count(N)!=N:
    K = K - 1
    B = [0]*N
    for i in range(N):
        for j in range(N):
            if A[j] >= abs(j-i):
                B[i] = B[i]+1
    A = B

print(' '.join(map(str,A)))

### FIXED CODE ###

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

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

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

import heapq
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    inst.append((tcnt % 2, fcnt))

f_total = sum([f for (_, f) in inst])
f_rem = [0] * (len(inst) + 1)
f_rem[len(inst)] = 0
for i in range(len(inst) - 1, -1, -1):
    f_rem[i] = f_rem[i + 1] + inst[i][1]
assert f_rem[0] == f_total


visited = set()


def reach():
    hp = [(0, rx, ry, 1, 0)]
    while hp:
        i, x, y, dx, dy = heapq.heappop(hp)

        dist = abs(gx - x) + abs(gy - y)
        # print(f"i={i} ({x},{y}) dist={dist}: inst={inst[i:]}")
        if i == len(inst):
            if dist == 0:
                return True
            continue
        if (i, x, y, dx, dy) in visited:
            continue
        visited.add((i, x, y, dx, dy))
        if dist > f_rem[i]:
            continue
        t, f = inst[i]
        if t:
            dy, dx = dx, -dy
        heapq.heappush(hp, (i + 1, x + f * dx, y + f * dy, dx, dy))
        heapq.heappush(hp, (i + 1, x - f * dx, y - f * dy, -dx, -dy))
    return False


print("Yes" if reach() else "No")


### FIXED CODE ###

"""Knapsack"""
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
s = input().rstrip()
gx, gy = map(int, input().split())
rx, ry = 0, 0
head, inst = 0, []
while head < len(s) and s[head] == "F":
    head += 1
    rx += 1

xlist, ylist = [], []
heading_x = True
while head < len(s):
    tcnt = 0
    while head < len(s) and s[head] == "T":
        tcnt += 1
        head += 1
    if head == len(s):
        break
    fcnt = 0
    while head < len(s) and s[head] == "F":
        fcnt += 1
        head += 1
    if ((tcnt % 2) == 1) ^ heading_x:
        heading_x = True
        xlist.append(fcnt)
    else:
        heading_x = False
        ylist.append(fcnt)


def fill(fs, goal_offset):
    f_total = sum(fs)
    if f_total < goal_offset:
        return False
    if f_total == goal_offset:
        return True
    f_diff = f_total - goal_offset
    if f_diff % 2 == 1:
        return False
    f_diff //= 2
    diffs = {0}
    for f in fs:
        for d in list(diffs):
            d2 = f + d
            if d2 > f_diff:
                continue
            if d2 == f_diff:
                return True
            diffs.add(d2)
    return False


if fill(xlist, abs(gx - rx)) and fill(ylist, abs(gy - ry)):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    ac = 0
    wa = 0
    a = []
    b = {}
    for _ in range(m):
        q, j = input().split()
        if q in a:
            continue
        if q not in a and j == 'AC':
            ac += 1
            a.append(q)
            if q in b:
                wa += b[q]
        else:
            if q not in b:
                b[q] = 0
            b[q] += 1
    print(ac, wa)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    ac = 0
    wa = 0
    b = defaultdict(lambda: 0)
    for _ in range(m):
        q, j = input().split()
        if b[q] != -1 and j == 'AC':
            ac += 1
            if q in b:
                wa += b[q]
                b[q] = -1
        else:
            if b[q] != -1:
                b[q] += 1
    print(ac, wa)

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

def main():
    N = int(input())
    ans = 0
    data = [i for i in range(1, N+1)]
    data_c = data.copy()
    tmp = data_c.pop(0)
    data_c.append(tmp)

    for i in range(N):
        ans += data[i]%data_c[i]

    print(ans)

    return 0
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    ans = (N-1)*N//2

    print(ans)

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

import numpy as np
n,q=map(int,input().split())
s=input()
e=[[0]*n for i in range(26)]
p=n
for i in range(n):
    e[ord(s[i])-ord("A")][i]+=1
h=np.array([1]*n)
for i in range(q):
    t,d=map(str,input().split())
    if d=="R":
        l=h*np.array(e[ord(t)-ord("A")])
        p-=l[-1]
        h=h-np.array(l)+np.array(np.hstack([[0], l[:-1]]))
    else:
        l=h*np.array(e[ord(t)-ord("A")])
        p-=l[0]
        h=h-np.array(l)+np.array(np.hstack([l[1:],[0]]))
print(p)

### FIXED CODE ###

n,q=map(int,input().split())
s="0"+input()+"0"
a=[list(input().split())for i in range(q)]
l=0
r=n+1
for i in range(q-1,-1,-1):
    t,d=a[i]
    if t==s[l] and d=="R":
        l-=1
    elif t==s[l+1] and d=="L":
        l+=1
    if t==s[r] and d=="L":
        r+=1
    elif t==s[r-1] and d=="R":
        r-=1
print(max(0,r-l-1))
### BUGGY CODE ###

n,k=map(int,input().split())
routes=list(map(int,input().split()))
dp=[float("inf") for i in range(n)]
dp[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            dp[j]=min(dp[j],dp[i]+abs(routes[i]-routes[j]))


print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
routes=list(map(int,input().split()))
dp=[float("inf") for i in range(n)]
dp[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            dp[j]=min(dp[j],dp[i]+abs(routes[i]-routes[j]))


print(dp[-1])