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

n = int(input())
a = list(map(int, input().split()))
line = []
for i in range(1,n):
    line.append(a.count(i))
line.append(0)
for i in range(len(line)):
    print(int(line[i]))


### FIXED CODE ###

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

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

n=int(raw_input())
t=a=1

for i in range(n):
    x,y=map(int,raw_input().split())
    if t<=x and a<=y:
        t=x
        a=y
    else:
        tmp=1
        while 1:
            if x*tmp>=t and y*tmp>=a:
                t=x*tmp
                a=y*tmp
                break
            tmp+=1
print t+a

### FIXED CODE ###

n=int(raw_input())
t=a=1

for i in range(n):
    x,y=map(int,raw_input().split())
    n=max((t+x-1)/x,(a+y-1)/y)
    t=n*x
    a=n*y
print t+a
### BUGGY CODE ###

s = input()

dp = [[0 for _ in range(4)] for _ in range(len(s) + 1)]
dp[len(s)][3] = 1

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    dp[i][3] = m * dp[i+1][3]
    dp[i][2] = m1 * dp[i+1][2] + m2 * dp[i+1][3]
    dp[i][1] = m1 * dp[i+1][1] + m3 * dp[i+1][2]
    dp[i][0] = m1 * dp[i+1][0] + m4 * dp[i+1][1]

n = 10 ** 9 + 7
ans = dp[0][0] % n
print(ans)

### FIXED CODE ###

s = input()

dp = [[0 for _ in range(4)] for _ in range(len(s) + 1)]
dp[len(s)][3] = 1
n = 10 ** 9 + 7

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    dp[i][3] = (m * dp[i+1][3]) % n
    dp[i][2] = (m1 * dp[i+1][2] + m2 * dp[i+1][3]) % n
    dp[i][1] = (m1 * dp[i+1][1] + m3 * dp[i+1][2]) % n
    dp[i][0] = (m1 * dp[i+1][0] + m4 * dp[i+1][1]) % n

ans = dp[0][0]
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]#足場iまでの最小コスト
for i in range(1,N):
    l=max(0,i-K)
    m=min([d+abs(H[i]-h) for d,h in zip(dp[l:i],H[l:i])])
    dp.append(m)
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]#足場iまでの最小コスト
for i in range(1,N):
    l=max(0,i-K)
    m=min([d+abs(H[i]-h) for d,h in zip(dp[l:i],H[l:i])])
    #m=min(map(lambda d,h:d+abs(H[i]-h),dp[l:i],H[l:i]))
    dp.append(m)
print(dp[-1])
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
B = []
C = []
for i in range(M):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

C_arr = []
for i in range(M):
    for _ in range(B[i]):
        C_arr.append(C[i])

C_arr.sort(reverse=True)

A.sort()
ans = []
for i in range(N):
	if i < len(C_arr):
		ans_item = max(A[i], C_arr[i])
	else:
		ans_item = A[i]
	ans.append(ans_item)

print(sum(ans))


### FIXED CODE ###

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

# Cについて大きい順にソート
BC.sort(key=lambda x: x[1], reverse=True)

temp = []
for i in range(M):
        # CiをBi個追加
    temp += [BC[i][1]] * BC[i][0]
    if len(temp) > N:
        break

A += temp
A.sort(reverse=True)

print(sum(A[:N]))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] * (N+1) # the largest number using i matches
for a in A:
    if count[a] <= N:
        dp[count[a]] = a
for i in range(N+1):
    if dp[i] == 0:
        continue
    for a in A:
        if i + count[a] <= N:
            dp[i+count[a]] = max(dp[i+count[a]], int(''.join(sorted(list(str(dp[i]) + str(a)), reverse=True))))
print(dp[N])



### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for _ in range(N+1)]
for i in range(N+1):
    if i > 0 and all(dp[i][j] == 0 for j in range(10)):
        continue
    for a in A:
        if i + count[a] <= N:
            ndp = list(dp[i])
            ndp[a] += 1
            ca = sum(ndp)
            cb = sum(dp[i+count[a]])
            if ca > cb:
                dp[i+count[a]] = ndp
            if ca == cb:
                for j in range(10)[::-1]:
                    if dp[i+count[a]][j] > ndp[j]:
                        break
                    if dp[i+count[a]][j] < ndp[j]:
                        dp[i+count[a]] = ndp
                        break
ans = ''
for i in range(10)[::-1]:
    ans += str(i) * dp[N][i]
print(ans)
### BUGGY CODE ###

#n = int(input())
#L = list(map(int, input().split()))
#import math
#import sys
#import heapq
#import fractions
#import bisect
#import numpy
#import queue
#import math
'''
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
n = int(input())   
l = list(map(int, input().split()))

l.sort(reverse=True)
ans=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        for m in range(j+1,n):
            if l[i]<l[j]+l[m]:
                ans+=1
print(ans)

### FIXED CODE ###

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def sol(n,l):
    import bisect
    l.sort()
    ans = 0
    #print(l)
    for i in range(n-1):
        for j in range(i+1,n):
            ji = l[j]+l[i]
            ind = bisect.bisect_left(l,ji)
            #print(i,j,ind,ind-j-1)
            ans += ind-j-1
    return ans


def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int, input().split()))
    print(sol(n,l))

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

a, b= map(int, input().split())
def W(x, y):
    w = []
    for i in range(1, min([x+1, y+1])):
        if x%i == 0 and y%i == 0:
            w.append(i)
        else:
            continue
    return w
ans = 0
for i in range(2, len(W(a, b))):
    for j in range(1, i-1):
        if W(a, b)[i] % W(a, b)[j] == 0:
            ans += 1
            break
        else:
            continue

print(len(W(a, b))-ans)

### FIXED CODE ###

import math
from collections import defaultdict


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    if 1 not in factor.keys():
        factor[1] += 1
    return factor


a, b = map(int, input().split())
ans = 0
for i in trial_division(a).keys():
    if i in trial_division(b).keys():
        ans += 1
print(ans)
### BUGGY CODE ###

# prd様のコードを参考にしました
# https://atcoder.jp/contests/abc091/submissions/3282677

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

ans = 0
for k in range(30):
    T = 2 ** k
    A_mod = sorted([a % (2 * T) for a in A])
    B_mod = sorted([b % (2 * T) for b in B])

    tmp = 0

    for a in A_mod:
        # k-bit目が立つ条件 -> [T, 2T), [3T, 4T)の間にai + bj がある
        # しゃくとりっぽいやつ
        r1, r2, r3 = 0, 0, 0
        while r1 < N and a + B_mod[r1] < T:
            r1 += 1
        while r2 < N and a + B_mod[r2] < 2 * T:
            r2 += 1
        while r3 < N and a + B_mod[r3] < 3 * T:
            r3 += 1

        # 差をとると、[T, 2T), [3T, 4T)の間に入っっている数が手に入る
        tmp += (r2 - r1) + (N - r3)

    if tmp % 2 == 1:
        ans += T

print(ans)


### FIXED CODE ###

# prd様のコードを参考にしました
# https://atcoder.jp/contests/abc091/submissions/3282677

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

ans = 0
for k in range(30):
    T = 2 ** k
    A_mod = sorted([a % (2 * T) for a in A])
    B_mod = sorted([b % (2 * T) for b in B])

    tmp = 0

    r1, r2, r3 = 0, 0, 0
    for a in reversed(A_mod):
        # k-bit目が立つ条件 -> [T, 2T), [3T, 4T)の間にai + bj がある
        # しゃくとりっぽいやつ
        # rを毎回初期化すれば小さいほうからaを見てもできるけど、同じ区間を何回も見ることになってしゃくとりにならずTLEする
        while r1 < N and a + B_mod[r1] < T:
            r1 += 1
        while r2 < N and a + B_mod[r2] < 2 * T:
            r2 += 1
        while r3 < N and a + B_mod[r3] < 3 * T:
            r3 += 1

        # 差をとると、[T, 2T), [3T, 4T)の間に入っっている数が手に入る
        tmp += (r2 - r1) + (N - r3)

    if tmp % 2 == 1:
        ans += T

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

#import numpy as np

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

for nn in range(n):
    sraw.append(sorted(input().encode()))

ans = 0

#s = np.sort(np.array(sraw), axis=0).tolist()
s = sorted(sraw)
#print(s)

l = len(s)

for ss in range(0, l):
    fl = 0
    #print("")
    for sss in range(ss+1, l):
        #print("{0} {1}".format(s[ss],s[sss]))
        if s[ss] == s[sss]:
            ans += 1
            fl = 1

        elif fl == 1:

            break


print(ans)


### FIXED CODE ###

n = int(input())
sraw = dict()

for nn in range(n):
    i = "".join(sorted(input()))
    if i in sraw:
        sraw[i] += 1
    else:
        sraw[i] = 1

ans = 0

for ss in sraw:
    ans += round(sraw[ss]*(sraw[ss]-1)/2)

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

import sys
input = sys.stdin.readline

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

need =[2,5,5,4,5,6,3,7,6]

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
  
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

### FIXED CODE ###

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

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
    
n=int(input())
ans=0
for i in range(1,n+1):
    ans+=i*len(make_divisors(i))

print(ans)
    

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    y=n//i
    ans+=i*(y*(y+1)//2)
print(ans)
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    dp[1] = 0 if 1 in A else 1  # 1段目の行き方を設定
    for i in range(2, N + 1):
        if i in A:
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    # 1段目のパターンを設定
    if tag == 1:
        dp[1] = 0
        if len(A) == 0:
            tag = -1
        else:
            tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


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

n=int(input())
a=list(map(int,input().split()))
c=0
b=a[0]
for i in range(1,n):
    b=b*a[i]

for i in range(100000):
    if b%2==0:
        b=b//2
        c+=1
print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(0,n):
    while a[i]%2==0:
        a[i]=a[i]//2
        c+=1
print(c)
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
U = [0]*n

def s(x):
    t = 0
    for i in range(x):
        t += i+1
    return t/x

for i in range(n):
    U[i] = s(P[i])

ans = 0
for i in range(0, k):
    ans += U[i]

for j in range(1, n-k+1):
    t = 0
    for i in range(j, j+k):
        t += U[i]
    if ans < t:
        ans = t
print(ans)


### FIXED CODE ###

import copy
n, k = map(int, input().split())
P = list(map(int, input().split()))
U = [0]*n

for i in range(n):
    U[i] = (P[i]+1)/2

ans = sum(U[:k])
t = copy.copy(ans)

for i in range(n-k):
    t =  t+U[k+i]-U[i]
    ans = max(ans, t)
    
print(ans)
### BUGGY CODE ###

from collections import deque

N, A, B, C, D = map(int, input().split(' '))
S = input()
blocks = [i+1 for i, s in enumerate([s for s in S]) if s == '#']
flag = False

que = deque([(A, B)])
while que:
    A, B = que.pop()
    if A == C and B == D:
        flag = True
        break
    for i in range(3):
        for j in range(3):
            if i == j == 0:
                continue
            if A+i <= C and B+j <= D and A+i != B+j and (A+i) not in blocks and (B+j) not in blocks:
                que.append((A+i, B+j))

if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N, A, B, C, D = map(int, input().split(' '))
S = input()
blocks = [i+1 for i, s in enumerate([s for s in S]) if s == '#']

if '##' in S[A-1:C] or '##' in S[B-1:D]:
    print('No')
elif C < D:
    if S[C-1] == '.' and S[D-1] == '.':
        print('Yes')
    else:
        print('No')
else:
    if '...' in S[max(0, B - 2):D+1]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
a=list(map(int,input().split()))
result = ''
for i in range(n):
    t = 0
    for j in range(n):
        if j != i:
            t ^= a[j]
    result += str(t) + ' '

print(result)


### FIXED CODE ###

n = int(input())
a=list(map(int,input().split()))
forward = []
back = []
result = ''
t = 0
for i in range(n):
    t ^= a[i]
    forward.append(t)
t = 0
for i in range(n-1, -1, -1):
    t ^= a[i]
    back.append(t)

for i in range(n):
    if i == 0:
        t = back[n-2]
    elif i == n-1:
        t = forward[n-2]
    else:
        t = forward[i-1] ^ back[n-2-i]
    result += str(t) + ' '

print(result)
### BUGGY CODE ###

"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math import gcd
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
l = A[0]
for i in range(1,N):
    l = (l*A[i])//gcd(l,A[i])

ans = 0
for a in A:
    ans += (l//a)%mod
    ans %= mod
print(ans)


### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
ddprint("q " + str(q))
for i in range(1,q):
    ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            heapq.heappush(tl,-a)
            suml += a
            a = -heapq.heappop(tl)
            suml -= a
            if a<root:
                a,root = root,a
            heapq.heappush(tr,a)
            sumr += a
            nr += 1
        else:
            heapq.heappush(tr,a)
            sumr += a
            a = heapq.heappop(tr)
            sumr -= a
            if a>root:
                a,root = root,a
            heapq.heappush(tl,-a)
            suml += a
            nl += 1
        ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        ddprint(tl)
        ddprint(tr)


### FIXED CODE ###

import heapq
#printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
#inm   = lambda:      map(int, input().split())
DBG = True  and False
#def ddprint(x):
#  if DBG:
#    print(x)

q = inn()
x = inl()
root = x[1]
b = x[2]
tl = []
tr = []
nl = nr = suml = sumr = 0
#ddprint("q " + str(q))
for i in range(1,q):
    #ddprint("i " + str(i))
    x = inl()
    if len(x)==1:
        z = sumr - suml - (root if nr>nl else 0) + b
        print("{} {}".format(root,z))
    else:
        a = x[1]
        b += x[2]
        if nl == nr:
            aa = -heapq.heappushpop(tl,-a)
            suml += a - aa
            if aa<root:
                aa,root = root,aa
            heapq.heappush(tr,aa)
            sumr += aa
            nr += 1
        else:
            aa = heapq.heappushpop(tr,a)
            sumr += a - aa
            if aa>root:
                aa,root = root,aa
            heapq.heappush(tl,-aa)
            suml += aa
            nl += 1
        #ddprint("b {} root {} nl {} nr {} suml {} sumr {}".format(b,root,nl,nr,suml,sumr))
        #ddprint(tl)
        #ddprint(tr)
### BUGGY CODE ###

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

for i in range(int(m/n),0,-1):
    if m % i == 0:
        print(i)
        break


### FIXED CODE ###

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

def yakusuu(n,m):
    for i in range(int(m/n),0,-1):
        if m % i == 0:
            print(i)
            break

yakusuu(n,m)
### BUGGY CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n - 1, k)
    ans -= dd.count(0) * divq
    ans -= dd[:divr].count(0)

    last = x + sum(dd) * divq + sum(dd[:divr])
    ans -= last // m - x // m

    print(ans)


### FIXED CODE ###

import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), np.int64)
nxm = [map(int, input().split()) for _ in range(q)]

for n, x, m in nxm:
    dd = d % m

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

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

from functools import reduce
from fractions import gcd

N,X=map(int,input().split())
x=[int(i) for i in input().split()]
x.append(X)

x2 = map(lambda y: y-min(x), x)

print(reduce(gcd,x2))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N,X=map(int,input().split())
x=[abs(int(i)-X) for i in input().split()]

print(reduce(gcd,x))
### BUGGY CODE ###

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

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
sim_sum = [0]*(10**5+1)
sim_sum[3] = 1
for i in range(5,10**5,2):
    if i in table and (i+1)//2 in table:
        sim_sum[i] = 1
    sim_sum[i] += sim_sum[i-2]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])

### FIXED CODE ###

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

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
sim_sum = [0]*(10**5+1)

for i in range(len(table)):
    if table[i]*2-1 in table:
        sim_sum[table[i]*2-1] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])
### BUGGY CODE ###

import numpy as np

n = int(input())
s = input() + '_'
    
dp = np.zeros((n+1,n+1),dtype=int)
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(dp.max())

### FIXED CODE ###

n = int(input())
s = input() + '_'
    
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(max(list(map(lambda x: max(x), dp))))
### BUGGY CODE ###

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

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

def calc_e(p):
    temp = 0.5 + 0.5 * p
    return temp

temp_max = 0
temp_i = 0

for i in range(N - K + 1):
    temp = sum(P[i:i+K])
    if temp_max <= temp:
        temp_max = temp
        temp_i = i


temp = 0
temp = calc_e(temp_max // K) * (K - 1) + calc_e(temp_max // K + temp_max % K)
print(temp)

### FIXED CODE ###


N,K = list(map(int,input().split()))
line = list(map(int,input().split()))

temp_num = sum(line[0:K])
temp_max = temp_num

for i in range(N - K):
    temp_num = temp_num - line[i] + line[i + K]
    if temp_num > temp_max:
        temp_max = temp_num


print((temp_max + K) / 2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)
dp = [[[-1 for i in range(three + 1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res

rec(one, two, three)
print(dp[one][two][three])


### FIXED CODE ###

import sys
from collections import Counter
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res *= 1.0/(i+j+k)

    dp[i][j][k] = res
    return res

c = Counter(a)
one, two, three = c[1], c[2], c[3]
print(rec(one, two, three))