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

N = int(input())
aA = sorted([int(_) for _ in input().split()],reverse=True)
aA1 = [ _ for _ in aA if _ % 2 ]
aA0 = [ _ for _ in aA if _ % 2 == 0 ]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(i+1,iL):
            if i in dsT or j in dsT:
                continue
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1

    return iC
iC = 0
iC += searchPair(aA1)
iC += searchPair(aA0)
print(iC)


### FIXED CODE ###

N = int(input())
dA1 ={}
dA0 ={}
def lenbin(a):
    return len(bin(a)) - 2
def addData(oDict,a):
    if a in oDict:
        oDict[a]+=1
    else:
        oDict[a]=1
for a in input().split():
    a = int(a)
    if a % 2 :
        addData(dA1,a)
    else:
        addData(dA0,a)
def searchPair(oD):
    iC = 0
    for a in sorted(oD.keys(),reverse=True):
        t = ( 1 << lenbin(a)) - a
        if t == a:
            iAT = oD[a] // 2
            iC += iAT
            oD[a] -= iAT *2
        elif t in oD:
            iAT = min(oD[a],oD[t])
            iC += iAT
            oD[a] -= iAT
            oD[t] -= iAT
    return iC
#iC = 0
#iC += searchPair(dA1)
#iC += searchPair(dA0)
print(searchPair(dA1)+searchPair(dA0))
### BUGGY CODE ###

#coding:utf-8

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

count = 0
r, g, b = 0, 0, 0

for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    elif i == 'B':
        b += 1

count = r * g * b

for i in range(n-2):
    si = s[i]
    for j in range(i+1,n-1):
        sj = s[j]
        nk = 2 * j - i
        if not nk < n:
            continue
        snk = s[nk]
        if {si, sj, snk} == {'R','G','B'}:
            count -= 1

print("{}".format(count))

### FIXED CODE ###

#coding:utf-8

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

count = 0
r, g, b = 0, 0, 0

for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    elif i == 'B':
        b += 1

count = r * g * b

for i in range(n-2):
    si = s[i]
    for j in range(i+1,n-1):
        sj = s[j]
        nk = 2 * j - i
        if not nk < n:
            break
        snk = s[nk]
        if {si, sj, snk} == {'R','G','B'}:
            count -= 1

print("{}".format(count))
### BUGGY CODE ###

ans = 1
ok = True
_n = int(input())
a = list(map(int,input().split()))
for i in a:
    ans *= i

if ans > 1e18:
    print(-1)
else :
    print(ans)

### FIXED CODE ###

ans = 1
ok1 = True
_n = int(input())
a = list(map(int,input().split()))
ok2 = False
if 0 in a:
    ok2 = True

for i in a:
    ans *= i
    if ans > 1e18:
        ok1 = False
        break

if ok2:
    print(0)
elif ok1:
    print(ans)
else :
    print(-1)
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
m = 1
for a in A:
  m *= a
  if m > 10**18:
    break
if min(A) == 0:
  m = 0
print(m if m <= 10**18 else -1)
### BUGGY CODE ###

binary = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741817, 147483634, 294967268, 589934536, 179869065, 359738130, 719476260, 438952513, 877905026, 755810045, 511620083, 23240159, 46480318, 92960636, 185921272, 371842544, 743685088, 487370169, 974740338, 949480669, 898961331, 797922655, 595845303, 191690599, 383381198, 766762396, 533524785, 67049563, 134099126, 268198252, 536396504]

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
max_len = len(format(max(a), "b"))
b = [0 for _ in range(max_len)]

for i in range(n):
    count = 0
    while a[i] > 0:
        b[count] += a[i]%2
        a[i] //= 2
        count += 1

result = 0
for i in range(max_len):
    r = b[i]*(n-b[i])%mod
    r = r*binary[i]%mod
    result += r
print(result%mod)

### FIXED CODE ###

import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)
### BUGGY CODE ###

n, m, l = map(int, input().split())
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
inf = 10**12
d = [[inf for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
dd = warshall_floyd(d)
ddd = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dd[i][j] <= l:
      ddd[i][j] = 1
dddd = warshall_floyd(ddd)
q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  if dddd[s-1][t-1] == inf:
    print(-1)
  else:
    print(dddd[s-1][t-1]-1)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
inf = 10**12
d = [[inf for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
dd = floyd_warshall(d)
ddd = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dd[i][j] <= l:
      ddd[i][j] = 1
dddd =floyd_warshall(ddd)
q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  if dddd[s-1][t-1] == inf:
    print(-1)
  else:
    print(int(dddd[s-1][t-1]-1))
### BUGGY CODE ###

import numpy as np
N, M, Q = map(int, input().split())

check = np.array([[0] * (N+1) for i in range(N+1)])

for i in range(M):
    l, r = map(int, input().split())
    check[r][l] += 1

# print(check)
for i in range(1, N+1):
    check[i] += check[i-1]
# print(check)

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += check[q][i] - check[p-1][i]
    print(ans)


### FIXED CODE ###

# import sys
import numpy as np
# input = sys.stdin.readline

def main():
    N, M, Q = map(int, input().split())

    check = np.zeros((N+1, N+1))

    for i in range(M):
        l, r = map(int, input().split())
        check[r][l] += 1

    # print(check)
    for i in range(1, N+1):
        check[i] += check[i-1]
    for i in range(1, N+1):
        check[:,i] += check[:,i-1]
    # print(check)

    for i in range(Q):
        p, q = map(int, input().split())
        print(int(check[q][q] - check[q][p-1] - check[p-1][q] + check[p-1][p-1]))

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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
W, V = read_col(N, 2)


dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

dp[0] = [0] * (K + 1)
for i in range(N + 1):
    dp[i][0] = 0

for sum_w in range(K + 1):
    for i in range(N):
        if sum_w - W[i] > -1:
            dp[i + 1][sum_w] = max(
                dp[i][sum_w],
                dp[i][sum_w - W[i]] + V[i]
            )
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

print(dp[-1][-1])


### FIXED CODE ###

import sys
read = sys.stdin.readline


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


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


import numpy as np

N = read_a_int()
ABC = np.array(read_matrix(N))
# A, B, C = read_col(N, 3)

dp = np.full((N, 3), -float('inf'))
# 0->a,1->b,2->c

dp[0, :] = ABC[0]

for i in range(N - 1):  # 範囲は怪しい後で考える
    # 幸福度足してないじゃん！
    dp[i + 1, 0] = (dp[i, 1:]+ABC[i+1, 0]).max()
    dp[i + 1, 1] = (dp[i, (0, 2)] + ABC[i+1, 1]).max()
    dp[i + 1, 2] = (dp[i, :2]+ABC[i+1, 2]).max()

# print(dp)
print(int(dp[N-1].max()))


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


# import numpy as np

N = read_a_int()
# ABC = np.array(read_matrix(N))
# # A, B, C = read_col(N, 3)

# dp = np.full((N, 3), -float('inf'))
# # 0->a,1->b,2->c

# dp[0, :] = ABC[0]

# for i in range(N - 1):
#     dp[i + 1, 0] = dp[i, 1:].max()+ABC[i+1, 0]
#     dp[i + 1, 1] = dp[i, (0, 2)].max() + ABC[i+1, 1]
#     dp[i + 1, 2] = dp[i, :2].max()+ABC[i+1, 2]

# # print(dp)
# print(int(dp[N-1].max()))

# TLEしたのでpypy3仕様にかきなおし

ABC = read_matrix(N)

# dp = np.full((N, 3), -float('inf'))
dp = [[-float('inf') for _ in range(3)] for _ in range(N)]
# 0->a,1->b,2->c

for i in range(3):
    dp[0][i] = ABC[0][i]

for i in range(N - 1):

    for j in range(3):
        iterlist = [0, 1, 2]
        iterlist.remove(j)
        dp[i+1][j] = max([dp[i][k] + ABC[i+1][j] for k in iterlist])

# print(dp)
print(int(max(dp[-1])))
### BUGGY CODE ###


H,W,M=map(int,input().split())

HSum=[0 for _ in range(H)]
WSum=[0 for _ in range(W)]


bombs = []
for _ in range(M):
	hi,wi = map(lambda x:int(x)-1,input().split())
	HSum[hi] += 1
	WSum[wi] += 1
	bombs.append( (hi,wi) )
# print(HSum)
# print(WSum)



curMax = 0

## 計算量多すぎ。。
# for h in range(H):
# 	for w in range(W):
# 		tmp = HSum[h] + WSum[w]
# 		if curMax <= tmp:
# 			if (h,w) in bombs:
# 				tmp -= 1
# 			curMax = max( curMax, tmp )

hMax = max(HSum)
wMax = max(WSum)
tmpMax = hMax + wMax

ans = 0

# hSumMaxOnly = [h for h, x in enumerate(HSum) if x == hMax]
# wSumMaxOnly = [w for w, y in enumerate(WSum) if y == wMax]

for h in [h for h, x in enumerate(HSum) if x == hMax]:
	if ans == tmpMax:
		break
	for w in [w for w, y in enumerate(WSum) if y == wMax]:
		if (h,w) in bombs:
			ans = tmpMax - 1
		else:
			ans = tmpMax
			break



print(ans)


### FIXED CODE ###


H,W,M=map(int,input().split())

HSum=[0 for _ in range(H)]
WSum=[0 for _ in range(W)]


bombs = set()
for _ in range(M):
	hi,wi = map(lambda x:int(x)-1,input().split())
	HSum[hi] += 1
	WSum[wi] += 1
	bombs.add( (hi,wi) )
# print(HSum)
# print(WSum)



curMax = 0

## 計算量多すぎ。。
# for h in range(H):
# 	for w in range(W):
# 		tmp = HSum[h] + WSum[w]
# 		if curMax <= tmp:
# 			if (h,w) in bombs:
# 				tmp -= 1
# 			curMax = max( curMax, tmp )

hMax = max(HSum)
wMax = max(WSum)
tmpMax = hMax + wMax

ans = 0

hSumMaxOnly = [h for h, x in enumerate(HSum) if x == hMax]
wSumMaxOnly = [w for w, y in enumerate(WSum) if y == wMax]

for h in hSumMaxOnly:
	if ans == tmpMax:
		break
	for w in wSumMaxOnly:
		if (h,w) in bombs:
			ans = tmpMax - 1
		else:
			ans = tmpMax
			break



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

from sys import stdin

n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
s = [str(i) for i in s]

mi = 10**10
s.append("W")

for i in range(len(s)-1):
    fi = s[:i].count("W")
    la = s[i+1:].count("E")
    mi = min(mi,fi+la)
print(mi)

### FIXED CODE ###

from sys import stdin
import bisect
from itertools import accumulate
import numpy as np

n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

mi = 10**10

li = [0]*n
lin = [0]*n

for i in range(len(s)):
    if s[i] == "W":
        li[i] = 1
    if s[n-i-1] == "E":
        lin[i] = 1

li = np.asarray(list(accumulate(li)))
lin = np.asarray(list(accumulate(lin)))[::-1]
lis = li+lin

lis.sort()

print(lis[0]-1)
### BUGGY CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
isinA = [0] * (a_ls[-1]+1)
for i in range(n):
    isinA[a_ls[i]] = 1

def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    divisors.pop()
    return divisors

ans = 0
for i in range(n):
    divisors = make_divisors(a_ls[i])
    not_divisible = True
    for j in range(len(divisors)):
        if isinA[divisors[j]]:
            not_divisible = False
    if i > 0:
        if a_ls[i-1] == a_ls[i]:
            not_divisible = False
    if i < n-1:
        if a_ls[i+1] == a_ls[i]:
            not_divisible = False
    if not_divisible:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
a_max = a_ls[-1]
times_ls = [0] * (a_max + 1)
divisible_ls = [0] * (a_max + 1)
for i in range(n):
    base = a_ls[i]
    times_ls[base] += 1
    times = 2
    while base*times <= a_max:
        divisible_ls[base*times] = 1
        times += 1
ans = 0
for i in range(1,a_max+1):
    if times_ls[i] == 1 and divisible_ls[i] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
 
list=[]
 
for i in range(1,n+1):
    if len(list) == 1 and i>int(n/i):
        ans=(list[-1][0]-1)+(list[-1][1]-1)
        break
    a=n%i

    if a == 0:
        if(i<n/i):
            list.append([i,int(n/i)])
            if list[-1][0] == list[-1][1]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
        else:
            list.append([int(n/i),i])
            if len(list) == 1:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
                break
            if list[-1]==list[-2]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
print(ans)

### FIXED CODE ###

import math

n = int(input())

for i in range(int(math.sqrt(n)), 0, -1):
  if n % i == 0:
    print(int(i + n / i - 2))
    break
### BUGGY CODE ###

from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


H, W = tuple(map(int, input().split()))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = []
for i in range(0, H):
    for j in range(0, W):
        if not grid[i][j]:
            black.append((i, j))

s_path = []
queue = deque([[(0, 0)]])
while not len(queue) == 0:
    path = queue.popleft()
    here = path[-1]
    if here == (H - 1, W - 1):
        s_path = path
        break;
    grid[here[0]][here[1]] = False
    arounds = get_arounds(here, grid, H, W)
    queue.extend(list(map(lambda a: path + [a], arounds)))
else:
    s_path = []

if len(s_path) == 0:
    print('-1')
else:
    print(H * W - len(s_path) - len(black))


### FIXED CODE ###

from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x + dx, y + dy) for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0))]
    return list(filter(lambda a: 0 <= a[0] < max_x and
                                 0 <= a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


H, W = tuple(map(int, input().split()))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

grid[0][0] = False
p_grid = {(0, 0): 0}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        grid[a[0]][a[1]] = False
        p_grid[a] = p_grid[here] + 1
    if not arounds:
        continue
    queue.extend(arounds)

if (H-1, W-1) in p_grid:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)
else:
    print(-1)
### BUGGY CODE ###

from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    Q=int(input())
    # n以下の素数のリストprimes
    n = 10**5
    primes = set(range(2, n + 1))

    # 合成数 x は p<=x**0.5を満たす素因子 p をもつという性質を利用
    for i in range(2, int(n ** 0.5 + 1)):
        primes.difference_update(range(i * 2, n + 1, i))
    primes = list(primes)

    for i in range(Q):
        l,r=map(int,input().split())
        A=[0]*(r+1)
        for j in range(1,r+1,2):
            if j in primes and (j+1)//2 in primes:
                A[j]=1
        # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
        B = list(accumulate(A))
        print(B[r]-B[l-1])




resolve()

### FIXED CODE ###

# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # n以下の素数のリストprimes
    n = 10**5
    primes = set(range(2, n + 1))

    # 合成数 x は p<=x**0.5を満たす素因子 p をもつという性質を利用
    for i in range(2, int(n ** 0.5 + 1)):
        primes.difference_update(range(i * 2, n + 1, i))
    primes = list(primes)

    L=[0]*10**5
    for i in primes:
        if (i+1)//2 in primes:
            L[i]=1

    from itertools import accumulate


    B = [0] + L
    B = list(accumulate(B))  # 累積和を格納したリスト作成

    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り

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


resolve()
### BUGGY CODE ###

N = int(input())
C = []
S = []
F = []

for _ in range(N - 1):
	tmp = list(map(int, input().split()))
	C.append(tmp[0])
	S.append(tmp[1])
	F.append(tmp[2])

def func(i, t):
	if i == N - 1:
		return t
	else:
		T = S[i]
		while T < t:
			T += F[i]
		return func(i + 1, T + C[i])

for i in range(N):
	print(func(i, 0))

### FIXED CODE ###

N = int(input())
C = []
S = []
F = []

for _ in range(N - 1):
	tmp = list(map(int, input().split()))
	C.append(tmp[0])
	S.append(tmp[1])
	F.append(tmp[2])

for i in range(N):
	t = 0
	for j in range(i, N - 1):
		if t < S[j]:
			t = S[j]
		elif t % F[j] != 0:
			t += F[j] - (t % F[j])
		t += C[j]
	print(t)
### BUGGY CODE ###

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

q = 0
if len(H) >= 2:
  for i in range(len(H)-1):
    for j in range(i+1, len(H)):
      if H[i] - 1 > H[j]:
        q += 1

if q == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

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

q, c = 0, 0
if len(H) >= 2:
  i = 0
  while i < len(H) - 1 and q == 0:
    if c <= H[i]:
      c = H[i]
    if c > H[i+1] + 1:
      q += 1
    i += 1
    
if q == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
# スペース区切りの整数の入力
ar = []
for i in range(n):
  ar.append("".join(sorted(input())))

#for t in ar:
#  print(t)
for i in range(n):
  for j in range(i+1, n):
    if ar[i] == ar[j]:
      ar[j] = ar[i]

count = 0
for i in range(n):
  for j in range(i+1, n):
    if ar[i] is ar[j]:
      count = count + 1
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())

# スペース区切りの整数の入力
ar = []
for i in range(N):
  l = list(input())
  l.sort()
  ar.append("".join(l).__hash__())

# 数を数える
list = {}
for i in ar:
  if i in list:
    list[i] = list[i] + 1
  else:
    list[i] = 1
  
count = 0
for i in list.values():
  n = i - 1
  count = count + int(((n * (n + 1)) / 2))

print(count)
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(lambda l: int(l)*(-1), input().split()))
L.sort()

result = 0
for i, a in enumerate(L[:-2:]):
    for ii, b in enumerate(L[i+1:-1:]):
        c_list = L[i+ii+2::]
        c_index = bisect_left(c_list, a-b)
        result += c_index

print(result)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(lambda l: int(l)*(-1), input().split()))
L.sort()

result = 0
for i, a in enumerate(L[:-2:]):
    for ii, b in enumerate(L[i+1:-1:]):
        c_list = L[i+ii+2::]
        c_index = bisect_left(c_list, a-b)
        result += c_index

print(result)