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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n,a,b =map(int,input().split())
mod = 10**9 +7

total = 2**n -1

total-=cmb(n,a)
total-=cmb(n,b)


print(total%mod)

### FIXED CODE ###

n,a,b =map(int,input().split())
mod =pow(10,9) +7

def comb(n,x):
    numerator = 1
    for i in range(n-x+1,n+1):
        numerator=  numerator * i  % mod
    
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator * j % mod
    
    d = pow(denominator,mod-2,mod)

    return numerator * d

a = comb(n,a)
b =  comb(n,b)

print( (pow(2,n,mod) - 1  - a - b) %mod)
### BUGGY CODE ###

s=input()
n=int(input())
a=[[i for i in input().split()] for l in range(n)]
c=0
for x in a:
    if x[0]=="1":c+=1
    if x[0]=="2":
        if c%2==1:s=s[::-1]
        c=0
        if x[1]=="1":s=x[2]+s
        else:s=s+x[2]
if c%2==1:s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
n=int(input())
a=[input() for _ in range(n)]

front=True
f=""
b=""

for q in a:
    if q=="1":front=not front;continue
    l=q.split()
    if l[1]=="1":
        if front:f=l[2]+f
        else:b=b+l[2]
    if l[1]=="2":
        if front:b=b+l[2]
        else:f=l[2]+f

print(f+s+b if front else (f+s+b)[::-1])
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
a_b = [_ for _ in range(a, b+1)]

cm = list(filter(lambda x: x%c == 0, a_b))
dm = list(filter(lambda x: x%d == 0, a_b))
cdm = list(filter(lambda x: x%c == 0 and x%d == 0, a_b))

print(len(a_b)-(len(cm)+len(dm))+len(cdm))

### FIXED CODE ###

def lcm(a,b):
    ab = a*b
    while b != 0:
        a, b = b, a%b
    return ab //a

def su(n,c,d):
    return n - n//c - n//d + n//lcm(c,d)
    
def main():
    a,b,c,d = map(int,input().split())
    print(su(b,c,d) - su(a-1,c,d))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

### FIXED CODE ###

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

s = input()
n = len(s)
prev = '2'
while True:
  s = s.replace('01', '')
  s = s.replace('10', '')
  if prev == s:
    break
  prev = s
print(n - len(s))


### FIXED CODE ###

s = input()

print(2*min(s.count('0'),s.count('1')))
### BUGGY CODE ###

import numpy as np

mod = 2019
mods_count = np.zeros(2019, dtype=np.int64)
indexes = list(range(2019))
indexes_10 = [index * 10 % mod for index in indexes]

mod = 2019
ans = 0
S = input()
for s in S:
    num = int(s)
    new = np.roll(mods_count, num)
    new[num] += 1

    ans += new[0]
    mods_count = np.zeros(2019, dtype=np.int64)
    mods_count[indexes_10] += new[indexes]

print(ans)


### FIXED CODE ###

from collections import Counter


mod = 2019
S = map(int, reversed(input()))

mods = [0]
num = 0
digit = 1
for s in S:
    num += s * digit
    num %= mod
    mods.append(num)
    digit = digit * 10 % mod

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)
### BUGGY CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def main():
	MOD = 10**9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)
		

	@lru_cache(None)
	def dp(mask):
		new = popcount(mask)
		if new == n: return 1
		cnt = 0
		for cand in range(n):
			bcand = 1 << cand
			if A[new][cand] and not (mask & bcand):
				cnt += dp(mask ^ bcand)
				cnt %= MOD
		return cnt % MOD
	print(dp(0))
	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def main():
	MOD = 10**9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)

	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n)-1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and not (mask & (1 << cand)):
				nmask = mask ^ (1 << cand)
				dp[nmask] += (dp[mask] % MOD)
				dp[nmask] %= MOD
	print(dp[-1]) 
	stdout.close()

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

N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
for _ in range(M):
    B, C = map(int, input().split(' '))
    A.extend([C]*B)
print(sum(sorted(A)[-N:]))

### FIXED CODE ###

N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
BC_list = []
for _ in range(M):
    B, C = map(int, input().split(' '))
    BC_list.append((B, C))
BC_list = sorted(BC_list, key= lambda x: x[1], reverse=True)

for b, c in BC_list:
    A.extend([c]*b)
    if len(A) > 2*N:
        break
print(sum(sorted(A)[-N:]))
### BUGGY CODE ###

"""
import sys
input = sys.stdin.readline
#"""

import scipy as sp

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

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

S = "A" + S
cs = sp.cumsum
ans = sp.zeros(Q,int)
D = sp.zeros(N+1,int)
cntM = sp.zeros(N+1,int)
sumM = sp.zeros(N+1,int)
M = []
C = []
for i,s in enumerate(S):
    if s=="D":
        D[i] = 1
    elif s=="M":
        M.append(i)
    elif s=="C":
        C.append(i-1)
D = cs(D)
for i in M:
    cntM[i] = 1
    sumM[i] = D[i]
cntM = cs(cntM)
sumM = cs(sumM)

for i in C:
    sMi = sumM[i]
    cMi = cntM[i]
    for j,k in enumerate(K):
        ik = max(0,i-k+1)
        ans[j] += (sMi-sumM[ik]) - D[ik]*(cMi-cntM[ik])
for out in ans:
    print(out)


### FIXED CODE ###

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

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
#dist_matrix = [[-1] * W for _ in range(H)]
dist_hash = {}
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      #dist_matrix[i][j] = 0
      dist_hash[i*W+j] = 0
      queue.append([i,j])
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.popleft()
  #max_value = dist_matrix[i][j]
  max_value = dist_hash[i*W+j]
  #cnt += 1
  #if i > 0 and dist_matrix[i-1][j] == -1:
  if i > 0 and (i-1)*W+j not in dist_hash:
    #dist_matrix[i-1][j] = max_value + 1
    dist_hash[(i-1)*W+j] = max_value + 1
    queue.append([i-1,j])
  #if i < H-1 and dist_matrix[i+1][j] == -1:
  if i < H-1 and (i+1)*W+j not in dist_hash:
    #dist_matrix[i+1][j] = max_value + 1
    dist_hash[(i+1)*W+j] = max_value + 1
    queue.append([i+1,j])
  #if j > 0 and dist_matrix[i][j-1] == -1:
  if j > 0 and i*W+j-1 not in dist_hash:
    #dist_matrix[i][j-1] = max_value + 1
    dist_hash[i*W+j-1] = max_value + 1
    queue.append([i,j-1])
  #if j < W-1 and dist_matrix[i][j+1] == -1:
  if j < W-1 and i*W+j+1 not in dist_hash:
    #dist_matrix[i][j+1] = max_value + 1
    dist_hash[i*W+j+1] = max_value + 1
    queue.append([i,j+1])
 
#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

def resolve():
    import math
    from collections import defaultdict
    n = int(input())
    a = list(set(map(int, input().split())))

    maxa = max(a)
    e = [0]*(maxa+1)
    for i in range(2, maxa+1):
        for j in range(i, maxa+1, i):
            if e[j] == 0:
                e[j] = i

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

    pair = False
    divisors = set([])
    for i in range(0, len(a)):
        test = a[i]
        divs = []
        while test > 1:
            divs.append(e[test])
            test //= e[test]
        divs = set(divs)
        if divs & divisors != set():
            pair = True
            break
        else:
            divisors = divs|divisors

    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 ###

# from .myutil import Combination


class Combination:
    mod = 0
    N = 0
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]

    def __init__(self, mod=10 ** 9 + 7, N=10 ** 9):
        self.mod = mod
        self.N = N
        for i in range(2, self.N + 1):
            self.g1.append((self.g1[-1] * i) % self.mod)
            self.inverse.append((-self.inverse[self.mod % i] * (self.mod // i)) % self.mod)
            self.g2.append((self.g2[-1] * self.inverse[-1]) % self.mod)

    def cmb(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % self.mod


n, a, b = map(int, input().split())
comb = Combination(10 ** 9 + 7, n)

total = (2 ** n) - comb.cmb(n, a) - comb.cmb(n, b) - 1

print(total)


### FIXED CODE ###

# from .myutil import Combination
from math import factorial

MOD = 10 ** 9 + 7
def Combination2(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) % MOD
    return ret * pow(factorial(r), MOD - 2, MOD) % MOD

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

total = pow(2, n, MOD) - Combination2(n, a) - Combination2(n, b) - 1
total %= MOD

print(total)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
def lcm(x,y):
    return (x * y) // gcd(x, y)
MOD = 10**9+7


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

l = reduce(lcm,a)
ans=0
for i in range(n):
    ans+=l//a[i]%MOD
    ans%=MOD

print(int(ans))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
def lcm(x,y):
    return (x * y) // gcd(x, y)
MOD = 10**9+7


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

l = reduce(lcm,a)%MOD
ans=0
for i in range(n):
    ans+=l*pow(a[i],MOD-2, MOD)
    ans%=MOD

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

import numpy as np

N = int(input())
S = np.array(list(input()))

r = (S == "R").sum()
g = (S == "G").sum()
b = (S == "B").sum()

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

print(r*g*b - cnt)

### FIXED CODE ###

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

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

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

print(r*g*b - cnt)
### BUGGY CODE ###

input_num = input()
input_list = input()
 
total_pow = 1
for num in input_list.split(" "):
  total_pow *= int(num)
 
if total_pow > 10**18:
  print("-1")
else:
  print(total_pow)

### FIXED CODE ###

import sys
input_num = input()
input_list = input()
 
total_pow = 1
for num in input_list.split(" "):
    total_pow *= int(num)
    if total_pow > 10**18:
        if "0" in input_list.split(" "):
            print("0")
        else:
            print("-1")
        sys.exit()

print(total_pow)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
L = set()
for i in range(n-1):
    if s[i:i+2] == "AC":
        L.add(i+1)

for i in range(q):
    l,r = map(int,input().split())
    print(len([i for i in L if l <= i and i < r]))


### FIXED CODE ###

n,q = map(int,input().split())
s = input().replace("AC","aC")
L = [0]*n
cnt = 0
for i in range(1,n):
    if s[i-1] == "a":
        cnt += 1
    L[i]=cnt
        
for i in range(q):
    l,r = map(int,input().split())
    print(L[r-1] - L[l-1])
### BUGGY CODE ###

def main():
    n, K = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = a.count(n)
    for k in range(K):
        an = [0] * n
        for i in range(n):
            if an[i] < n:
                an[i] += 1
            for j in range(1, a[i]+1):
                if i - j >= 0 and an[i-j] < n:
                    an[i-j] += 1
                    if an[i-j] == n:
                        cnt += 1
                if i + j < n and an[i+j] < n:
                    an[i+j] += 1
                    if an[i+j] == n:
                        cnt += 1
        else:
            a = an
            if cnt == n:
                break
    print(*a)
main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(k):
        imos = [0] * (n + 1)
        for i in range(n):
            imos[max(0, i - a[i])] += 1
            imos[min(n, i + a[i] + 1)] -= 1
        for i in range(1, n):
            imos[i] += imos[i-1]
        imos.pop()
        a = imos
        if min(a) == n:
            break 
    print(*a)
main()
### BUGGY CODE ###

def isP(n):
	for i in prime:
		if i >= n:
			break
		if n%i == 0:
			return False
	return True

r = int(10000001**0.5)
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(2,s):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]:
		prime.append(i)

while 1:
	try:
		n = input()
		if n == 0: break
		i = n-(1-n%2)
		while i > 12:
			p6 = isP(i-6)
			if not isP(i-8) or not isP(i-2):
				if not p6:
					i -= 10
				else:
					i -= 4
				continue
			if isP(i) and p6:
				print i
				break
			i -= 2
	except:
		pass

### FIXED CODE ###

ref = [[[10,8],[4,4]],[[10,2],[4,2]]]
r =10000001
p = [1]*r
p[0]= p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])
		
while 1:
	try:
		n = input()
		if n == 0: break
		n -= 1-n%2
		while any(not p[n-i] for i in [0,2,6,8]):
			n -= ref[p[n-2]][p[n-6]][p[n-8]]
		print n
	except:
		pass
### BUGGY CODE ###

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n+1);

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[n-1] % 998244353)


### FIXED CODE ###

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n+1);

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    dp[i] %= 998244353
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[-2] % 998244353)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for l in range(1, N//2+2):
    s, t = S[:l], S[l:]
    dp = [[0 for _ in range(N-l+1)] for _ in range(l+1)]
    for i in range(l):
        for j in range(N-l):
            if (s[i] == t[j]):
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    if (dp[l][N-l] > ans):
        ans = dp[l][N-l]
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = 0
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if (S[i] == S[j]):
            dp[i][j] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = 0
ans = 0
for i in range(N):
    for j in range(N):
        now = min(dp[i][j], abs(i-j))
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d

"""
import sys
from sys import stdin
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5))
    for l, r in queries:
        ans = 0
        for i in range(l, r+1, 2):
            if i in primes and ((i+1)//2) in primes:
                ans += 1
        print(ans)


def main(args):
    queries = []
    Q = int(input())
    # Q = 0
    # queries.append((1, 99999))
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d

"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes



def solve(queries):
    primes = set(create_prime_list(10**5))
    dp = [0] * (100000 + 1)

    p_num = 0
    for i in range(1, 100000, 2):
        if i in primes and ((i+1)//2) in primes:
            p_num += 1
        dp[i] = p_num

    for l, r in queries:
        if l == 1:
            ans = dp[r]
        else:
            ans = dp[r] - dp[l-2]
        print(ans)



def main(args):
    queries = []
    Q = int(input())
    # Q = 0
    # for _ in range(100000):
    #     queries.append((1, 99999))
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))

    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

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

### FIXED CODE ###

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

n=int(input())
a=list(map(int,input().split()))
sum_=[a[0]]
num=a[0]
for i in range(1,n):
    num=num+a[i]
    sum_.append(num)
count={}
for i in range(n):
    if sum_[i] in count.keys():
        count[sum_[i]]+=1
    else:
        count[sum_[i]]=1
ans=0
for i in count.values():
    ans+=i*(i-1)//2
if 0 in count.keys():
    ans+=count[0]
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
sum_=[a[0]]
num=a[0]
for i in range(1,n):
    num=num+a[i]
    sum_.append(num)
count={}
for i in range(n):
    if sum_[i] in count.keys():
        count[sum_[i]]+=1
    else:
        count[sum_[i]]=1
ans=0
for i in count.values():
    ans+=i*(i-1)//2
if 0 in count.keys():
    ans+=count[0]
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    h = [i for i in map(int, input().split())]

    ans = 0
    for i in range(2, n):
        for j in range(n+1-i):
            if sorted(h[j:j+i], reverse=True) == h[j:j+i]:
                ans = i-1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    if N == 1:
        print(0)
        quit()

    start = 0
    moves = []
    for i in range(N-1):
        if H[i] >= H[i+1]:
            continue
        moves.append(i - start)
        start = i + 1

    if H[N-2] >= H[N-1]:
        moves.append(i - start + 1)
    print(max(moves))


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

n = int(input())
A = list(map(int, input().split()))
B = {}
C = {}
for a in A:
    if a in C:
        continue
    c = A.count(a)
    C[a] = c
    B[a] = c * (c - 1) / 2

s = int(sum(B.values()))
for a in A:
    print(int(s - C[a] + 1))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
C = {}
for a in A:
    if a in C:
        C[a] += 1
    else:
        C[a] = 1

s = int(sum(c * (c - 1) / 2 for c in C.values()))
for a in A:
    print(int(s - C[a] + 1))