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

def resolve():
    import math
    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass

    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    a = sorted(a)
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = set(divisor(a[i]))
        nxt = divisors | divs
        if len(nxt) != len(divs) + len(divisors):
            pair = True
            break
        else:
            divisors = nxt
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")

resolve()

### FIXED CODE ###

def resolve():
    import math
    n = int(input())
    a = list(set(map(int, input().split())))
    maxa = max(a)

    ggcd = a[0]
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break

    pair = False

    c = [0] * (10**6+ 1)
    for i in a:
        c[i] += 1

    for i in range(2, maxa+1):
        cnt = 0
        for j in range(i, maxa+1, i):

            cnt += c[j]
        if cnt > 1:
            pair = True

    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()
### BUGGY CODE ###

mod = 10**9 + 7

N,M = map(int,input().split())
S = input().split()
T = input().split()

dp = [[-1]*(M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = 1
for j in range(1,M+1):
    dp[0][j] = 1

for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
        dp[i][j] %= mod

ans = dp[N][M]
print(ans)

### FIXED CODE ###

mod = 10**9 + 7

N,M = map(int,input().split())
S = input().split()
T = input().split()

dp = [[-1]*(M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = 1
for j in range(1,M+1):
    dp[0][j] = 1

for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
        dp[i][j] %= mod

ans = dp[N][M]
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
total = 0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, N + 1):
    g1.append(( g1[-1] * i ) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

for i in range(n-k+1):
    for j in range(i+k-1,n):
        total += cmb(j-i-1,k-2,mod)*(a[j]-a[i])
        total %= mod
print(total)

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
total = 0
def cmb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**5
g1 = [1,1]
g2 = [1,1]
inverse = [0,1]

for i in range(2, N + 1):
    g1.append((g1[-1]*i) % mod)
    inverse.append((-inverse[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1]*inverse[-1]) % mod)

for i in range(n-k+1):
    total += cmb(n-i-1,k-1,mod)*(a[n-i-1]-a[i])
    total %= mod
print(total)
### BUGGY CODE ###

from collections import Counter
n = int(input())
S = [input() for _ in range(n)]
ans = 0

for i in range(n):
  S[i] = Counter(S[i])

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

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
sorted_word = {}

for i in range(n):
  word = ''.join(sorted(input()))
  sorted_word.setdefault(word, 0)
  sorted_word[word] += 1

def pair_num(n):
  return (n * (n - 1)) // 2

print(sum(map(pair_num, sorted_word.values())))
### BUGGY CODE ###

N = int(input())
ch = []
for i in range(N):
    ch.append(''.join(sorted(list(input()))))
cnt = 0
ch = sorted(ch)
tmp = 0
for i in range(N):
    for j in range(i+1,N):
        if ch[i]==ch[j]:
            cnt += 1
        else:
            tmp = j
            break
print(cnt)

### FIXED CODE ###

import collections
N = int(input())
ch = []
for i in range(N):
    ch.append(''.join(sorted(list(input()))))
cnt = 0
ch = sorted(ch)
# print(set(ch))
# print(len(ch)-len(set(ch)))
cnt = collections.Counter(ch)
# se = list(set(ch))
# print("se:"+str(se))
h={}
sum=0
for i in range(N):
    h[i]=sum+i
    sum+=i
sum = 0
for i in cnt.values():
    sum += h[i-1]
print(sum)
### BUGGY CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    N = 14
    K = 2
    S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  i = 0
  lenSC = len(SC) - 1
  ans = 0
  while i <= lenSC:
    cnt = 0
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    k += 1
    cnt = sum(SC[i:k])
    if ans < cnt:
      ans = cnt
    i += 2

  print(ans)

main()

### FIXED CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()
### BUGGY CODE ###

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
already = []
for i in range(n):
  while will_go:
    now = will_go.pop()
    already.append(now)
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        if root not in already:
          ans[root] += tmp
          will_go.append(root)
        
print(*ans)

### FIXED CODE ###

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
ald = [True]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
ald[0] = False
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    for root in tree[now]:
      if ald[root]:
        ald[root] = False
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)
### BUGGY CODE ###

import sys

n = sys.stdin.readline()
l = list(map(int, sys.stdin.readline().split()))
tmp = 1000000000000000000

ans = 1
for i in l:
    if i == 0:
        ans = 0
        break

    ans *= i

if ans <= 1000000000000000000:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

import sys

n = sys.stdin.readline()
l = list(map(int, sys.stdin.readline().split()))
tmp = 1000000000000000000

if 0 in l:
    print(0)
else:
    ans = 1
    for i in l:
        ans *= i
        if 1000000000000000000 < ans:
            break
    if ans <= 1000000000000000000:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans1 = 0
for i in range(n+1):
  ans2 = int(a * i / b) - a * int(i / b)
  ans1 = max(ans1, ans2)
print(ans1)


### FIXED CODE ###

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

a = input()
a = list(a)
prev = '0'
i = 0
c = 0
d = True
while(d):
  if(a != []):
    if(i > 0 and a[i] != prev):
      a.pop(i-1)
      a.pop(i-1)
      c += 2
      i = 0
      continue
    prev = a[i]
    if(i == len(a) - 1):
      break
  else:
    d = False 
  i += 1
print(c)

### FIXED CODE ###

a = input()

z = 0
i = 0
for b in a:
  if(b == '0'):
    z += 1
  else:
    i += 1
if(z >= i):
  print(i * 2)
else:
  print(z * 2)
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
p = list(int(x)-1 for x in input().split())
c = list(map(int, input().split()))
score = -10**9
his = [0]*(n+1)
for i in range(n):
  rec = np.array([0])
  here = i
  cnt = 0
  for _ in range(k):
    here = p[here]
    rec = np.append(rec,c[here])
    cnt += 1
    if here == i:
      break
  rec = np.cumsum(rec)
  s = max(rec[1:])
  ps = rec[-1]*(k//cnt)+max(rec[0:k%cnt+1])
  s = max(ps,s)
  score = max(s,score)
print(score)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    loop = accum[l-1]
    accum=[0]+accum
    for x in range(1,l+1):
        if loop<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)
### BUGGY CODE ###

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
a.sort()
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if i in a:
            dp[i]=0
            a.pop(0)
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
### BUGGY CODE ###

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

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())


for i in range(Q):
    ans = 0
    subseq = S[l[i]-1:r[i]]
    for j in range(len(subseq)-1):
        if (subseq[j] == 'A')and(subseq[j+1] == 'C'):
            ans += 1
    print(ans)

### FIXED CODE ###

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

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

ans = [0] * N


for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        ans[i+1] = ans[i] + 1
    else:
        ans[i+1] = ans[i]
        
for j in range(Q):
    print(ans[r[j]-1]-ans[l[j]-1])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
L = []
for x in range(1,N+1):
    for y in range(1,N+1):
       if(x == y):
           L.append(x)
       elif(x % y == 0):
           L.append(y)
       elif(y % x == 0):
           L.append(x)
       else:
           L.append(gcd(x,y))
for x in L:
    for z in range(1,N+1):
       if(x == z):
           ans += x 
       elif(x % z == 0):
           ans += z
       elif(z % x == 0):
           ans += x
       else:
           ans += gcd(x,z)
print(ans) 

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
L = []
s_dict = {}
for x in range(1,N+1):
    for y in range(1,N+1):
       if(x == y):
           L.append(x)
           s_dict[(x,y)] = x
       elif(x % y == 0):
           L.append(y)
           s_dict[(x,y)] = y
       elif(y % x == 0):
           L.append(x)
           s_dict[(x,y)] = x
       else:
           tmp = gcd(x,y)
           L.append(tmp)
           s_dict[(x,y)] = tmp

for x in L:
    for z in range(1,N+1):
        ans += s_dict[(x,z)]
        
print(ans)
### BUGGY CODE ###

def f_d():
    import numpy as np
    n = int(input())
    if n == 1:
        print(0)
    else:
        print(np.cumsum(range(1, n))[-1])

if __name__ == "__main__":
    f_d()


### FIXED CODE ###

def f_d():
    n = int(input())
    n -= 1
    if n%2==0:
        print(n*((n-2)//2+1)+n//2)
    else:
        print(n*((n-1)//2+1))

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

N,HP=map(int,input().split())
listK=[]
listN=[]

for i in range(N):
    k,n=map(int,input().split())
    listK.append(k)
    listN.append(n)
listK.sort(reverse=True)
listN.sort(reverse=True)
cnt=0
for j in range(N):
    if listN[j]>=max(listK):
        HP-=listN[j]
        cnt+=1
        if HP<=0:
            print(cnt)
            exit()
    else:
        break

cnt+=int((HP+listK[0]-1)/(listK[0]))
print(cnt)


### FIXED CODE ###

n,h=map(int,input().split())
slash=[]
throw=[]
for i in range(n):
    x,y=map(int,input().split())
    slash.append(x)
    throw.append(y)
 
slash.sort(reverse=True)
throw.sort(reverse=True)
attack=0
for i in range(n):
    if throw[i]>=slash[0]:
        h-=throw[i]
        attack+=1
        if h<=0:
            print(attack)
            exit()
    else :
        break
 
attack+=int((h+slash[0]-1)/(slash[0]))
print(attack)
### BUGGY CODE ###

H, N = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))
# print(AB)
f_inf = float('inf')
dp = [f_inf] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in AB:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))
# print(AB)
f_inf = float('inf')
dp = [f_inf] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in AB:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[H])
### BUGGY CODE ###

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

for i in range(A, B+1):
    if i - A + 1 <= K or B - i + 1 <= K:
        print(i)
    else:
        continue

### FIXED CODE ###

A, B, K = map(int, input().split())
candidate1 = [i for i in range(A, A+K) if i <= B]
candidate2 = [i+1 for i in range(B-K, B) if i+1 >= A]

ans = list(sorted(list(set(candidate1+candidate2))))
ans = [str(ans[i]) for i in range(len(ans))]

print('\n'.join(ans))
### BUGGY CODE ###

A, B, N = [int(i) for i in input().split()]
ans = 0
for i in range(A*B):
    x = N - i
    if x < 0:
        break
    tmp = int(A * (x % B / B) - (A * x % B) / B)
    if tmp >= ans:
        ans = tmp
print(ans)

### FIXED CODE ###

A, B, N = [int(i) for i in input().split()]
ans = 0
if N < B:
    ans = int(( A * (N % B) - (A * N) % B) / B)
else:
    tmp_ = int(( A * (N % B) - (A * N) % B) / B)
    x = (N - N % B - 1)
    tmp = int(( A * (x % B) - (A * x) % B) / B)
    ans = max(tmp, tmp_)
print(ans)
### BUGGY CODE ###

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

left = -10**10
right = 10**10

def get_score(b):
    score = 0
    for i in range(N):
        score += abs(A[i]-b-i)
    return score

while(right > left + 1):
    mid = (left+right) // 2
    if get_score(mid+1) - get_score(mid) < 0:
        left = mid
    else:
        right = mid

print(get_score(right))
        

### FIXED CODE ###

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

left = -10**10
right = 10**10

def get_score(b):
    score = 0
    for i in range(N):
        score += abs(A[i]-b-i)
    return score

while(right > left + 1):
    mid = (left+right) // 2
    if get_score(mid+1) - get_score(mid) < 0:
        left = mid
    else:
        right = mid

print(get_score(right))
### BUGGY CODE ###

l, r = [int(e) for e in input().split()]
m = 2019
for i in range(l, r):
  for j in range(i + 1, r + 1):
    t = (i * j) % 2019
    if t < m:
      m = t
print(m)

### FIXED CODE ###

l, r = [int(e) for e in input().split()]
m = 2019
for i in range(l, r):
  ir = i % 2019
  for j in range(i + 1, r + 1):
    t = (ir * j) % 2019
    if t < m:
      m = t
    if m == 0:
      break
  if m == 0:
    break
print(m)
### 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
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
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
P = LIST()

acc = [0]*N
for i in range(N):
	su = (P[i]*(P[i]+1)/2)/P[i]
	acc[i] = su

ma = 0
for i in range(N - K + 1):
	ma2 = 0
	for j in range(K):
		ma2 += acc[i+j]
	if ma < ma2:
		ma = ma2

print(ma)

### 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
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
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
P = LIST()

acc = [0]*N
for i in range(N):
	su = (P[i]*(P[i]+1)/2)/P[i]
	acc[i] = su

accs = [0]*N
accs[0] = acc[0]
for i in range(1, N):
	accs[i] = accs[i - 1] + acc[i]

ma = 0
for i in range(K - 1, N):
	ma2 = 0
	if i == K - 1:
		ma2 = accs[i]
	else:
		ma2 = accs[i] - accs[i - K]
	if ma < ma2:
		ma = ma2

print(ma)
### BUGGY CODE ###

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

result = []

def prime_number(n):
    for i in range(2, n+1):
        if i * i > n:
            return True
        if n%i == 0:
            return False
    return n != 1

for i in range(N):
    res = 0
    for j in range(L[i][0], L[i][1]+1):
        if prime_number(j) and prime_number((j+1)//2):
            res += 1
    result.append(res)

for res in result:
    print(res)

### FIXED CODE ###

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    table = [ i for i in range(n+1) if is_prime[i]]
    return table, is_prime

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

prime, flag = sieve(10 ** 5)
number = [0 for i in range(10 ** 5+1)]

for i in range(2, 10 ** 5):
    if flag[i] and flag[(i+1)//2]:
        number[i] += 1
        
for i in range(1, 10 ** 5):
    number[i] += number[i-1]
        
result = []
            
for i in range(N):
    res = number[L[i][1]] - number[L[i][0]-1]
    result.append(res)

for res in result:
    print(res)
### BUGGY CODE ###

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

MOD = 1000000007
ans = 0

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

print(ans % MOD)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

MOD = 1000000007
ans = 0

k = 0
s = [0] * n
for i in range(n-1, 0, -1):
    k += a[i] % MOD
    s[i] = k

for i in range(n-1):
    ans += a[i] * s[i+1]

ans = ans % MOD

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

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

ans = 0
for i in range(N):
    S = A[:]
    del(S[i])
    for j in range(N -1):
        for k in range(j+1,N -1):
            if(S[j] == S[k]):
                ans += 1
            else:
                pass
    print(ans)
    ans = 0


### FIXED CODE ###

import collections

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

C = collections.Counter(a)
total = 0
for i in C.keys():
    total += C[i] * (C[i] - 1) // 2
for i in range(n):
    A = a[i]
    print(total - C[A] + 1)
### BUGGY CODE ###

# ひとまず毎回ソートするバージョン

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

for i in range(m):
	max_card, num = list(map(int, input().split() ))

	values.sort()
	for j in range(max_card):
		if values[j] < num:
			values[j] = num
		else:
			break

print (sum(values))

### FIXED CODE ###

from operator import itemgetter
n, m = list(map(int, input().split() ))
values = list(map(int, input().split() ))
values.sort()

card_change = [list(map(int, input().split() )) for _ in range(m)]
card_change.sort(key = itemgetter(1))
# 変更後の数をkeyとしてソート

# X枚書き換えるとして、Xを全探索する方針で書いてみる
now = sum(values)
ans = sum(values)
idx = m - 1
for x in range(n):
	now -= values[x]

	card_change[idx][0] -= 1 # 変更可能枚数
	now += card_change[idx][1] # 変更後の値

	if now > ans:
		ans = now

	if card_change[idx][0] == 0:
		idx -= 1
		if idx < 0:
			break

print(ans)