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

mod = 1000000007
eps = 10**-9
inf = 10**9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XYP = []
    for _ in range(N):
        XYP.append(tuple(map(int, input().split())))

    dx = [[inf] * (1<<N) for _ in range(N)]
    dy = [[inf] * (1<<N) for _ in range(N)]
    for i in range(1 << N):
        L = []
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(XYP[j][0])
                Yline.append(XYP[j][1])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[j][i] = min(dx[j][i], abs(x - XYP[j][0]))
                dy[j][i] = min(dy[j][i], abs(y - XYP[j][1]))

    ans = [float("inf")] * (N+1)
    for i in range(3**N):
        M = i
        L = []
        k = 0
        ix = iy = 0
        for j in range(N):
            if M%3 == 1:
                k += 1
                ix += 1 << j
            elif M%3 == 2:
                k += 1
                iy += 1 << j
            M //= 3
        cost = 0
        for j in range(N):
            p = XYP[j][2]
            cost += min(dx[j][ix], dy[j][iy]) * p
        ans[k] = min(ans[k], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        x, y, p = map(int, input().split())
        X.append(x)
        Y.append(y)
        P.append(p)

    dx = [[inf] * N for _ in range(1<<N)]
    dy = [[inf] * N for _ in range(1<<N)]
    for i in range(1 << N):
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(X[j])
                Yline.append(Y[j])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[i][j] = min(dx[i][j], abs(x - X[j]))
                dy[i][j] = min(dy[i][j], abs(y - Y[j]))

    ans = [inf] * (N+1)
    beki = [1<<j for j in range(N)]
    for i in range(3**(N-1)):
        M = i
        k = 0
        ix = iy = 0
        J = []
        for j in range(N-1):
            M, m = divmod(M, 3)
            if m == 0:
                J.append(j)
            elif m == 1:
                k += 1
                ix += beki[j]
            else:
                k += 1
                iy += beki[j]
        for x in range(3):
            kk = k
            ix_ = ix
            iy_ = iy
            if x == 0:
                J.append(N-1)
            elif x == 1:
                kk += 1
                ix_ += beki[N-1]
            else:
                kk += 1
                iy_ += beki[N-1]
            cost = 0
            for j in J:
                p = P[j]
                cost += min(dx[ix_][j], dy[iy_][j]) * p
            ans[kk] = min(ans[kk], cost)
    for c in ans:
        print(c)


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


from collections import defaultdict
import heapq


def dijkstra(n, s, edges):
    dist = [float('inf') for _ in range(n)]
    dist[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    while len(q):
        d, p = heapq.heappop(q)
        if dist[p] < d:
            continue
        for e in edges[p]:
            if d + 1 < dist[e]:
                dist[e] = d + 1
                heapq.heappush(q, (dist[e], e))
    return dist


def submit():
    n, x, y = map(int, input().split())
    
    edges = {i: [] for i in range(n)}
    for i in range(n - 1):
        edges[i].append(i + 1)
        edges[i + 1].append(i)
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
    
    dist_list = {}
    for s in range(n):
        dist_list[s] = dijkstra(n, s, edges)

    count = defaultdict(int)
    for i in range(n):
        dist = dist_list[i]
        for j in range(i + 1, n):
            count[dist[j]] += 1

    for i in range(1, n):
        print(count[i])


submit()

### FIXED CODE ###

def submit():
    n, x, y = map(int, input().split())

    count = {i: 0 for i in range(1, n)}
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            # i, j <= X, or Y <= i, j
            if (i <= x and j <= x) or (x <= i and y <= j):
                d = j - i
            
            # X < i, j < Y
            if x < i and j < y:
                d = min(j - i, i - x + 1 + y - j)
            
            # i <= X and X < j < Y
            if i <= x and x < j < y:
                d = min(j - i,
                        x - i + 1 + y - j)            

            # X < i < Y and Y <= j
            if x < i < y and y <= j:
                d = min(j - i,
                        j - y + 1 + i - x)

            if i <= x and y <= j:
                d = min(j - i,
                        x - i + j - y + 1)
            count[d] += 1            
            

    for i in range(1, n):
        print(count[i])

submit()
### BUGGY CODE ###

N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for i in range(N):
    tmp += S[i]*10**i
    cnt[tmp%P] += 1
if P==2 or P==5:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S):
        if int(i) in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    d=i*pow(10,n,P)
    tmp =(tmp+d)%P
    cnt[tmp] += 1
if P in [2,5]:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S):
        if i in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from itertools import permutations

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

n, m ,r = input_list()
road = input_list()
road = [x-1 for x in road]
d = [[float('inf')] * n for i in range(n)]
for i in range(n) :
    d[i][i] = 0
for i in range(m) :
    a, b, c = input_list()
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

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])

ans = float('inf')
for p in permutations(road) :
    dist = 0
    for i in range(r-1) :
        dist += d[p[i]][p[i+1]]
    if ans > dist :
        ans = dist

print(ans)

### FIXED CODE ###

from itertools import permutations

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

def main() :
    n, m ,r = input_list()
    road = input_list()
    road = [x-1 for x in road]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(n) :
        d[i][i] = 0
    for i in range(m) :
        a, b, c = input_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c

    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                dist = d[i][k]+d[k][j]
                if d[i][j] > dist :
                    d[i][j] = dist

    ans = float('inf')
    for p in permutations(road) :
        dist = 0
        for i in range(r-1) :
            dist += d[p[i]][p[i+1]]
        if ans > dist :
            ans = dist

    print(ans)

main()
### BUGGY CODE ###

def main():
    """
    ワーシャルフロイドで経由したときに変更がないことを確認する
    変更がある場合、
        最短経路ではないため条件を満たさない
    変更がない場合、
        経由の経路でも最短距離になるケースを除いて距離を計算する
    """
    N = int(input())
    a = [None] * N
    total = 0
    no_need = 0
    for i in range(N):
        a[i] = list(map(int, input().split()))
        total += sum(a[i])

    for k in range(N):
        # from
        for i in range(N):
            # to
            for j in range(N):
                # compare from-to / from-経由地点-to
                if i == k or j == k:
                    continue
                d = a[i][k] + a[k][j]
                if a[i][j] > d:
                    return -1
                elif a[i][j] == d:
                    # 経由して同じであれば必要ない
                    no_need += d

    # 対称なので半分にする
    return (total - no_need) // 2

if __name__ == '__main__':
    answer = main()
    print(answer)


### FIXED CODE ###

def main():
    """
    ワーシャルフロイドで経由したときに変更がないことを確認する
    変更がある場合、
        最短経路ではないため条件を満たさない
    変更がない場合、
        経由の経路でも最短距離になるケースを除いて距離を計算する
    """
    N = int(input())
    a = [None] * N
    total = 0
    for i in range(N):
        a[i] = list(map(int, input().split()))
        total += sum(a[i])

    for k in range(N):
        for i in range(N):
            for j in range(N):
                # compare from-to / from-経由地点-to
                d = a[i][k] + a[k][j]
                if a[i][j] > d:
                    return -1

    # 不要判定
    v = [[False] * N for _ in range(N)]
    no_need = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == k or j == k:
                    continue
                if not v[i][j] and (a[i][j] == a[i][k] + a[k][j]):
                    no_need += a[i][j]
                    v[i][j] = True

    # 対称なので半分にする
    return (total - no_need) // 2

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

import sys
def input(): return sys.stdin.readline().strip()
S = input()
Q = int(input())
flag = True
for i in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag = not flag
    else:
        if flag:
            if q[1] == '1':
                S = q[2] + S
            else:
                S += q[2]
        else:
            if q[1] == '1':
                S = S + q[2]
            else:
                S = q[2] + S
if not flag:
    S = S[::-1]
print(S)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
S = input()
Q = int(input())
flag = True
f = ''
b = ''
for i in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag = not flag
    else:
        if flag:
            if q[1] == '1':
                f = q[2] + f
            else:
                b += q[2]
        else:
            if q[1] == '1':
                b += q[2]
            else:
                f = q[2] + f
S = f + S + b
if not flag:
    S = S[::-1]
print(S)
### BUGGY CODE ###

from bisect import bisect,bisect_left
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = [0]*29

for k in range(29):
    a = sorted([a%(2**(k+1)) for a in A]+[a%(2**(k+1))-2**(k+1) for a in A])
    for b in B:
        b_k = b%(2**(k+1))
        ans[k] += bisect(a,2**(k+1)-1-b_k)-bisect_left(a,2**k-b_k)
        ans[k] %= 2

print(sum([ans[k]*2**k for k in range(29)]))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.int32(input().split())
B = np.int32(input().split())

ans_arr = np.zeros(29,int)
for k in range(29):
    a = np.sort(A%(2**(k+1)))
    b = B%(2**(k+1))
    ans_arr[k] += np.sum(np.searchsorted(a,2**(k+1)-1-b,side='right')-np.searchsorted(a,2**k-b))
    ans_arr[k] += np.sum(N-np.searchsorted(a,3*2**k-b))
    ans_arr[k] %= 2

ans = 0
for k in range(29):
    ans += ans_arr[k]*2**k

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

def main():
    N, K, Q, *A = map(int, open(0).read().split())
    print("\n".join(["Yes" if Q < K + A.count(i)
                     else "No" for i in range(1, N + 1)]))
    return


main()


### FIXED CODE ###

from sys import stdin
from collections import Counter

lines = stdin.readlines()

N, K, Q = map(int, lines[0].split())
ans = [0] * N
A = Counter((int(i) - 1 for i in lines[1:]))
for k in A.keys():
    ans[k] += A[k]
print("\n".join(("Yes" if Q < K + a
                 else "No" for a in ans)))
### BUGGY CODE ###

n,m=[int(_) for _ in input().split()]
a=sorted([int(_) for _ in input().split()])
for iii in range(m):
  b,c=[int(_) for _ in input().split()]
  for jjj in range(b):
    if a[jjj]<c:
      a[jjj]=c
  a=sorted(a)
print(sum(a))

### FIXED CODE ###

from heapq import heappush, heappop
n,m=map(int,input().split())
hq=[]
for _ in input().split():
  heappush(hq,(-int(_),1))
for iii in range(m):
  b,c=map(int,input().split())
  heappush(hq,(-c,b))
s=0
for iii in range(n):
  a=heappop(hq)
  s-=a[0]
  if a[1]!=1:
    heappush(hq,(a[0],a[1]-1))
print(s)
### BUGGY CODE ###

import collections

n = int(input())
x = input()
dic = collections.defaultdict(int)
#dic_count = collections.defaultdict(int)
one_count = x.count("1")

for i in range(1,n+1):
    cnt = 0
    nm = bin(i).count("1")
    tmp = i
    while tmp:
        tmp %= nm
        nm = bin(tmp).count("1")
        cnt += 1
    dic[i] = cnt

if one_count == 1:
    cnt = 0
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            num = int(x,2) + 2 ** (n - i - 1)
            num %= (one_count+1)
            if num != 0:
                print(dic[num]+1)
            else:
                print(1)
else:
    for i in range(n):
        tmp_count = one_count
        num = int(x,2)
        if x[i] == "1":
            num -= 2 ** (n - i - 1)
            tmp_count -= 1
        else:
            num += 2 ** (n - i - 1)
            tmp_count += 1
        num %= tmp_count
        if num != 0:
            print(dic[num]+1)
        else:
            print(1)


### FIXED CODE ###

import collections
n = int(input())
x = input()

num_of_one = x.count("1")

#xの中に1が1つもない時
if num_of_one == 0:
    for i in range(n):
        print(1)
#xの中に1が1つの時(1を取り除くと0個になる)
elif num_of_one == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            #1が2個なので偶数なら余り0
            if x[-1] == "0" and i != n-1:
                print(1)
            #奇数なら1回1を経由
            else:
                print(2)
else:
    dic = collections.defaultdict(int)
    #0からnまでの回数を予め求めて辞書に格納
    for i in range(n):
        tmp_p = i

        cnt = 0
        while tmp_p:
            tmp_p %= bin(tmp_p).count("1")
            cnt += 1
        dic[i] = cnt


    #2冪を num_of_one ± 1 で割った余りの配列を用意しておく
    bi_mod_p = [1 % (num_of_one+1)]
    bi_mod_m = [1 % (num_of_one-1)]
    for i in range(1,n):
        bi_mod_p.append((bi_mod_p[-1] * 2) % (num_of_one+1))
        bi_mod_m.append((bi_mod_m[-1] * 2) % (num_of_one-1))

    #xと逆順なので合わせる
    bi_mod_p.reverse()
    bi_mod_m.reverse()

    #xの10進表記を num_of_one ± 1 で割った余りを用意する
    sum_p = 0
    sum_m = 0
    for i in range(n):
        if x[i] == "1":
            sum_p += bi_mod_p[i]
            sum_p %= (num_of_one+1)
            sum_m += bi_mod_m[i]
            sum_m %= (num_of_one-1)
    tmp = 0
    for i in range(n):
        # 0 -> 1 の変化。1が増えるのでpの方を使う
        if x[i] == "0":
            tmp = sum_p + bi_mod_p[i]
            tmp %= (num_of_one+1)

        # 1 -> 0 の変化。1が減るのでmの方を使う
        else:
            tmp = sum_m - bi_mod_m[i]
            if tmp < 0:
                tmp += (num_of_one-1)
            tmp %= (num_of_one-1)
        print(dic[tmp]+1)
### BUGGY CODE ###

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

comb = 1
mod = 10**9+7
for i in range(min(K-2, N*M-K)):
    comb *= (N*M-2-i)
    comb //= i+1

comb %= mod
x = (N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2
y = (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2
ans = (x+y)*comb
print(ans%mod)

### FIXED CODE ###

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

mod = 10**9+7
a = 1
b = 1
for i in range(min(K-2, N*M-K)):
    a *= (N*M-2-i)
    a %= mod
    b *= i+1
    b %= mod
comb = a * pow(b, mod - 2, mod) % mod

ans = (((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)*comb)%mod
print(ans)
### BUGGY CODE ###

import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N+1))
for _ in range(M):
  a, b = map(int, input().split())
  G.add_edge(a, b)

paths = nx.shortest_path(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(paths[i][1])





### FIXED CODE ###

import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()

G.add_edges_from(tuple(map(int, input().split())) for _ in range(M))

dist = nx.shortest_path_length(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(min((dist[j], j) for j in nx.all_neighbors(G, i))[1])
### BUGGY CODE ###

n = int(input())

if n == 1:
    print(0)
elif n == 2:
    print(1)
else:
    print(sum(range(1, n)))

### FIXED CODE ###

n = int(input())

if n == 1:
    print(0)
elif n == 2:
    print(1)
else:
    print((1 + n - 1) * (n - 1) // 2)
### BUGGY CODE ###

#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
 
""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""
 
"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""
 
"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""
 
# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""
 
# 二分探索
"""import bisect # 二分探索
print(A,bisect.bisect_left(A,4))
print(C,n - bisect.bisect_right(C,4))
print(sum(bisect.bisect_left(A,b) * (n-bisect.bisect_right(C,b)) for b in B))"""
 
# 円周率 pi
"""import math
pi_ = math.pi"""
 
# エラトステネスの篩
"""def Erato(n):
    prime = []
    is_prime = [True] * (n+1)
    p = 0
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
      if is_prime[i] == True:
        prime.append(i)
        p += 1
        for j in range(2 * i,n+1,i):
          is_prime[j] = False
    return p"""
 
def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def main():
  k = int(input())
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        ans += gcd(a,gcd(b,c))
  print(ans)
if __name__ == '__main__':
  main()

### FIXED CODE ###

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def main():
  k = int(input())
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        ans += gcd(a,gcd(b,c))
  print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = ls.count(max(set(ls),key=ls.count))
for x in set(ls):
    if ls.count(x) == counter:
        res.append(x)
r = sorted(res)
print("\n".join(r))

### FIXED CODE ###

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common()
for x in counter:
    if x[1] == counter[0][1]:
        res.append(x[0])
print("\n".join(sorted(res)))
### BUGGY CODE ###

N,M=map(int, input().split())
A = [int(input()) for i in range(M)]

mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
    if i in A:
        continue
    if i==1:
        dp[1]=dp[0]
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=mod
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

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

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

### FIXED CODE ###

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

N=int(input())
an=list(map(int,input().split()))
s=sum(an)
l=[]
for i in range(1,N):
    b = sum(an[:i])
    l.append(abs(s-2*b))
print(min(l))

### FIXED CODE ###

N=int(input())
an=list(map(int,input().split()))
s=sum(an)
b = an[0]

l=[]
a = abs(s-2*b)
for i in range(1,N-1):
    b = b + an[i]
    a=min(a,abs(s-2*b))
print(a)
### BUGGY CODE ###

n = int(input())
l = []

for i in range(n):
    a = input()
    if not a in l:
        l.append(a)
        
print(len(l))

### FIXED CODE ###

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

l = sorted(a)

count = 1
for i in range(n - 1):
    if l[i] != l[i + 1]:
        count += 1
    
print(count)
### BUGGY CODE ###

import math
from functools import lru_cache

n=int(input())
@lru_cache()
def sosu(l):
  if l ==2:
    return 1
  elif l % 2==0 or l==1 or l==3/2:
    return 0
  else:
    for d in range(3, math.floor(math.sqrt(l))+1,2):
      if l % d == 0:
        return 0
        break
    else:
      return 1

li=[]
for j in range(1,100001):
  li.append(sosu(j)*sosu((j+1)/2))

for i in range(n):
  a,b=[int(i) for i in input().split()]
  print(sum(li[a-1:b]))

### FIXED CODE ###

import math
from functools import lru_cache

n=int(input())
@lru_cache()
def sosu(l):
  if l ==2:
    return 1
  elif l % 2==0 or l==1 or l==3/2 or l==0:
    return 0
  else:
    for d in range(3, math.floor(math.sqrt(l))+1,2):
      if l % d == 0:
        return 0
        break
    else:
      return 1

m=0
li=[]
for j in range(0,100001):
  m+=sosu(j)*sosu((j+1)/2)
  li.append(m)

for i in range(n):
  a,b=[int(i) for i in input().split()]
  print(li[b]-li[a-1])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
d={}
for li in l:
  if li in d:
    d[li]+=1
  else:
    d[li]=1
l=list(set(l))
l.sort()
ans=0
for i in range(len(l)):
  for j in range(i+1):
    ls=[li for li in l[:j+1] if li>l[i]-l[j]]
    for lsi in ls:
      if l[i]==l[j] and l[j]==lsi:
        ans+=d[l[i]]*(d[l[i]]-1)*(d[l[i]]-2)//6
        #print(str(ans)+' '+str(l[i])+' '+str(l[j])+' '+str(lsi))
      elif l[i]==l[j]:
        ans+=d[l[i]]*(d[l[i]]-1)*d[lsi]//2
      elif l[j]==lsi:
        ans+=d[l[i]]*d[l[j]]*(d[l[j]]-1)//2
      else:
        ans+=d[l[i]]*d[l[j]]*d[lsi]
print(ans)


### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
import bisect
ans=0
for i in range(n):
  for j in range(i):
    index=bisect.bisect_right(l,l[i]-l[j])#このindexよりも右側のものでかつjより左のものが当てはまるもの
    ans += max(j - index,0)
print(ans)