Harryxun/stf_run huggingface dataset:
n = int(input())
win = {}
# key:勝者 value:keyに負けた人(set)
for i in range(n - 1):
    a = int(input())
    a -= 1
    if a not in win.keys():win[a] = set()
    win[a].add(i+1)

def dfs(winner):
    if winner not in win.keys():return 0
    losers = win[winner]
    storong = len(losers)
    deeps = []
    for loser in losers:
        deeps.append(dfs(loser))
    deeps.sort(reverse = True)
    deep = 1
    for i,d in enumerate(deeps):
        deep = max(deep, i+1 + d)
    return deep

print(dfs(0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
win = {}
# key:勝者 value:keyに負けた人(set)
for i in range(n - 1):
    a = int(input())
    a -= 1
    if a not in win.keys():win[a] = set()
    win[a].add(i+1)

def dfs(winner):
    if winner not in win.keys():return 0
    losers = win[winner]
    storong = len(losers)
    deeps = []
    for loser in losers:
        deeps.append(dfs(loser))
    deeps.sort(reverse = True)
    deep = 1
    for i,d in enumerate(deeps):
        deep = max(deep, i+1 + d)
    return deep

print(dfs(0))
import math
a,b=int(input()),float(input())
x=a*b
print(math.floor(x))

### FIXED CODE ###

A, B = input().split()
A, B = int(A), int(B.replace('.', ''))
print(A * B // 100)
a, b, x=map(int, input().split())
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)
print(90-math.degrees(math.atan(ans)))

### FIXED CODE ###

a, b, x=map(int, input().split())
if a*a*b==x:
  print(0)
  exit()
import math
if 2*x/(a*b)>=a:
  ans=a/(2*b-2*x/(a**2))
else:
  ans=2*x/(a*b**2)
print(90-math.degrees(math.atan(ans)))
n = int(input())
a = map(int, input.split())
b = map(int, input.split())
c = map(int, input.split()) 
former = -10
satisfy = 0
for i in a:
    print(i)
    satisfy += b[i-1]
    if i == former + 1:
        satisfy += c[i-2]
    former = i
print(satisfy)



### FIXED CODE ###

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

former = -10
satisfy = 0
for i in a:
    satisfy += b[i-1]
    if i == former + 1:
        satisfy += c[i-2]
    former = i
print(satisfy)
n = input()

if n == 'A':
  print('T')
  
elif n == 'T'
  print('A')
  
elif n == 'C'
  print('G')
  
elif n == 'G'
  print('C')



### FIXED CODE ###

n = input()

if n == 'A':
  print('T')
  
elif n == 'T':
  print('A')
  
elif n == 'C':
  print('G')
  
elif n == 'G':
  print('C')
N, A = map(int, input().split())
X = [int(a) for a in input().split()]
PO = [x-A for x in X if x > A]
NE = [A-x for x in X if x < A]
ZE = N - len(PO) - len(NE)

Y = [1] + [0] * (N*50)
Z = [1] + [0] * (N*50)

for i in PO:
    for j in range(len(Y) - A)[::-1]:
        Y[i+j] += Y[j]
for i in NE:
    for j in range(len(Z) - A)[::-1]:
        Z[i+j] += Z[j]

ans = -1
for i in range(len(Y)):
    ans += Y[i] * Z[i] * (2**ZE)
print(ans)

### FIXED CODE ###

N, A = map(int, input().split())
X = [int(a) for a in input().split()]
PO = [x-A for x in X if x > A]
NE = [A-x for x in X if x < A]
ZE = N - len(PO) - len(NE)

Y = [1] + [0] * 3000
Z = [1] + [0] * 3000

for i in PO:
    for j in range(2800)[::-1]:
        Y[i+j] += Y[j]
for i in NE:
    for j in range(2800)[::-1]:
        Z[i+j] += Z[j]

ans = -1
for i in range(len(Y)):
    ans += Y[i] * Z[i] * (2**ZE)
print(ans)
a,b,x = map(int,input().split())

ans = 0
for i in range(1,10):
　　n = (x - b*i)//a
　　if 10**(i-1) <= n < 10**i:
　　　　ans = n
　　elif n >= 10**i:
　　　  ans = 10**i - 1
  
if x >= a*10**9+b*10:
       ans =10**9
print(ans)

### FIXED CODE ###

s = input()

m = {'SUN':7,'MON':6,'TUE':5,'WED':4,'THU':3,'FRI':2,'SAT':1}

print(m[s])
n = int(input())
h = list(map(int, input().split()))
cnt = 0
move_cnt = []
for i in range(n-1):
   if h[i] >= h[i+1]:
      cnt += 1
   else:
      move_cnt.append(cnt)
      cnt = 0
print(max(move_cnt))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
cnt = 0
ans = 0
for i in range(n-1):
   if h[i] >= h[i+1]:
      cnt += 1
      ans = max(ans, cnt)
   else:
      cnt = 0
print(ans)
n = int(input())
ab = list(map(int, input().split()))

if n == 1:
    print("Hello World")
if n == 2:
    print(ab[0] + ab[1])



### FIXED CODE ###

n = int(input())
if n == 2:
    a = int(input())
    b = int(input())

if n == 1:
    print("Hello World")
if n == 2:
    print(a + b)
N = int(input())
lst_monsters = map(int, input().split())

import math
from functools import reduce

def gcd_list(lst):
    return reduce(math.gcd, lst)

ans = gcd_list(lst_monsters)
print(ans)

### FIXED CODE ###

# import math
import fractions
from functools import reduce

def gcd_list(lst):
    # return reduce(math.gcd, lst)
    return reduce(fractions.gcd, lst)

N = int(input())
lst_monsters = map(int, input().split())
print(gcd_list(lst_monsters))
def even_case(input_list) -> int:
    input_list.sort()

    for i in range(1, len(input_list), 2):
        if input_list[i] // 2 == 1 and input_list[i] != input_list[i-1]:
            return 0

    ans = 2 ** (n//2)

    return ans


def odd_case(input_list) -> int:
    input_list.sort()

    if input_list[1] == 0:
        return 0

    for i in range(2, len(input_list), 2):
        if input_list[i] // 2 == 0 and input_list[i] != input_list[i-1]:
            return 0

    ans = 2 ** ((n-1) // 2)

    return ans

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

if n % 2 == 0:
    print(even_case(input_list))
else:
    print(odd_case(input_list))

### FIXED CODE ###

def even_case(input_list) -> int:
    input_list.sort()

    if input_list[0] == 0: return 0


    for i in range(1, len(input_list), 2):
        if input_list[i] % 2 == 0 or input_list[i] != input_list[i-1]:
            return 0

    ans = 2 ** (n//2)

    return ans


def odd_case(input_list) -> int:
    input_list.sort()

    if input_list[0] != 0: return 0

    if len(input_list) == 1: return 1

    if input_list[1] == 0: return 0

    for i in range(2, len(input_list), 2):
        if input_list[i] % 2 == 1 or input_list[i] != input_list[i-1]:
            return 0

    ans = 2 ** ((n-1) // 2)

    return ans

n = int(input())
input_list = list(map(int, input().split()))
math = 10 ** 9 + 7

if n % 2 == 0:
    result = even_case(input_list)
else:
    result = odd_case(input_list)

print(result % math)
a,b,cmap(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-a-b)

### FIXED CODE ###

a,b,c=map(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-(a-b))
n,m=map(int,input().split())
sc=sorted([list(map(int,input().split())) for i in range(m)])
ans=[0,0,0]
res=True
ans[sc[0][0]-1]=sc[0][1]
for i in range(1,m):
    if sc[i][0]==sc[i-1][0] and sc[i][1]!=sc[i-1][1]:
        res=False
        break
    else:
        ans[sc[i][0]-1]=sc[i][1]

ans2=int("".join([str(i) for i in ans])) if res and not (n>1 and ans[0]==0) else -1
print(ans2)


### FIXED CODE ###

n,m=map(int,input().split())
sc=sorted([list(map(int,input().split())) for i in range(m)])
ans=[0 for i in range(n)]
res=True
for i in range(m):
    if (i>0 and sc[i][0]==sc[i-1][0] and sc[i][1]!=sc[i-1][1]) or (n>1 and sc[i][0]==1 and sc[i][1]==0):
        res=False
        break
    else:
        ans[sc[i][0]-1]=sc[i][1]

if n>1 and ans[0]==0:
    ans[0]=1

ans2=int("".join([str(i) for i in ans])) if res else -1
print(ans2)
N = int(input)

a_s = input().split()

for i in ragne(3*N):
  a_s[i] = int(a_s[i])
  
a_s = sorted(a_s)

a_1 = a_s[:N]
a_2 = a_s[N:]

ans = sum(a_2[0::2])

print(ans)

### FIXED CODE ###

N = int(input())

a_s = input().split()

for i in range(3*N):
  a_s[i] = int(a_s[i])
  
a_s = sorted(a_s)

a_1 = a_s[:N]
a_2 = a_s[N:]

ans = sum(a_2[0::2])

print(ans)
n, h, w = map(int, input().split())
print((n - h + 1) * (n - w + 1))

### FIXED CODE ###

n = int(input())
h = int(input())
w = int(input())
print((n - h + 1) * (n - w + 1))
S = list(input())
c = set(S)
all_ar = list("abcdefghijklmnopqrstuvwxyz")
if len(c) == 26:
    print(-1)
    exit()
for i in range(26):
    if not all_ar[i] in c:
        print(''join(S)+all_ar[i])
        exit()

### FIXED CODE ###

s = input()
if len(s) < 26:
    for i in range(26):
        c = chr(ord("a")+i)
        if c not in s:
            print(s+c)
            exit()
else:
    for i in reversed(range(1,26)):
        if s[i-1] < s[i]:
            s1 = s[0:i-1]
            for j in range(26):
                c = chr(ord("a")+j)
                if c > s[i-1] and c not in s1:
                    print(s1+c)
                    exit()
    print(-1)
import sys
t='X'
for e in sys.stdin:
 for i in'0123456789'[(e[0]==t)*(e[1]!='+')or('+X'in e)*not('+X='in e)or('=X'in e)*(e[-2]!='='):]:
  if eval(e.replace(t,i).replace('=','==')):print(i);break
 else:print('NA')


### FIXED CODE ###

import sys
p,t='+X'
for e in sys.stdin:
 for i in'0123456789'[(e[0]==t)*(e[1]!=p)or('+X'in e)*('+X='not in e):]:
  l,r=e.replace(t,i).split('=')
  if sum(map(int,l.split(p)))==int(r):print(i);break
 else:print('NA')
import sys

def main(argv):
    A = int(argv[0])
    B = int(argv[1])
    C = int(argv[2])
    print(judge(A, B, C))

def judge(A, B, C):
    if (A < C and A < B) or (C < A and B < A):
        return 'Yes'
    else:
        return 'No'

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


### FIXED CODE ###

import sys

def main():
    argv = input().split()
    A = int(argv[0])
    B = int(argv[1])
    C = int(argv[2])
    print(judge(A, B, C))

def judge(A, B, C):
    if (A < C and C < B) or (C < A and B < C):
        return 'Yes'
    else:
        return 'No'

if __name__ == '__main__':
    main()
from math import gcd


class Eratosthenes: # エラトステネスの篩
    def __init__(self, N) # 素数リスト生成 O(n*log(log n))
        is_prime = [0, 0] + [1] * (N - 1)
        for i in range(int(N**0.5) + 1):
            if is_prime[i] == 0:
                continue
            for j in range(i * 2, N + 1, i):
                is_prime[j] = 0
        self.prime_list = [i for i, pi in enumerate(is_prime) if pi == 1]


    def factor(self, NUM):  # 高速素因数分解 O(log num)
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(NUM)
        return PRIME


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')


### FIXED CODE ###

from math import gcd


def eratosthenes(n):
    prime = []
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data


def factorize(N):  # 素因数分解
    for p in prime_list:
        if p * p > N:
            break
        if N % p == 0 and (p in num):
            print('setwise coprime')
            exit()
        while N % p == 0:
            N //= p
            num.add(p)
    if N > 1:
        if N in num:
            print('setwise coprime')
            exit()
        num.add(N)


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    factorize(ai)
else:
    print('pairwise coprime')
import sys

def initRMQ(n, D):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(2147483647)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    return query(a, b + 1, 0, 0, n)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 2147483647

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((1 + r)/2))
    vr = query(a, b, k*2 + 2, int((1 + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, q = map(int, input().split())

    D = []
    n_ = initRMQ(n, D)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findMin(x, y))



### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)


def initRMQ(n, D):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(2147483647)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    return query(a, b + 1, 0, 0, n_)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 2147483647

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, q = map(int, input().split())

    D = []
    n_ = initRMQ(n, D)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findMin(x, y))
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
DIV = 10**9+7

def main():
    B = [0]*(M+1)
    for i in range(M+1):
        if i==0:
            B[i] = A[i]-1
        elif i==M:
            B[i] = N-A[i-1]-1
        else:
            B[i] = A[i] - A[i-1] - 2
    min_B = min(B)
    if min_B<0:
        return 0
    
    max_B = max(B)
    F = [1]*(max_B+1)
    for i,f in enumerate(F):
        if i<2:
            pass
        else:
            F[i] = F[i-2] + F[i-1]
    ans = 1
    for b in B:
        ans *= F[b]
        ans %=DIV
    return ans

print(main())


### FIXED CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
DIV = 10**9+7

def main():
    if M>0:
        B = [0]*(M+1)
        for i in range(M+1):
            if i==0:
                B[i] = A[i]-1
            elif i==M:
                B[i] = N-A[i-1]-1
            else:
                if A[i]==A[i-1]:
                    B[i] = 0
                else:
                    B[i] = A[i] - A[i-1] - 2
    else:
        B = [N]
    min_B = min(B)
    if min_B<0:
        return 0
    
    max_B = max(B)
    F = [1]*(max_B+1)
    for i in range(max_B+1):
        if i<2:
            pass
        else:
            F[i] = F[i-2] + F[i-1]
    ans = 1
    for b in B:
        ans *= F[b]
        if ans >= DIV:
            ans %= DIV
    return ans

print(main())
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combi(n,r,mod=10**9+7):
    fac = [0]*(n+1)
    fac[0] = 1
    fac[1] = 1
    for i in range(2,n+1):
        fac[i] = fac[i-1] * i % mod
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

N,K = map(int,input().split())
for j in range(1,K+1):
    print(combi(N-K+1,j) * combi(K-1,j-1) % mod)

### FIXED CODE ###

mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

fac = [0]*(N+1)
fac[0] = 1
fac[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1] * i % mod

def combi(n,r,mod=10**9+7):
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

for j in range(1,K+1):
    if N - K + 1 < j:
        print(0)
    else:
        print(combi(N-K+1,j) * combi(K-1,j-1) % mod)
x,y=map(int,input().solit())
if 2*x<=y and y%2==0 and 4*x>=y:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

x,y=map(int,input().split())
if 2*x<=y and y%2==0 and 4*x>=y:
    print('Yes')
else:
    print('No')
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6 + 1

dp = [1 for i in range(amax)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

cnt = col.Counter(a)

ans = 0
for num in a:
    if dp[num] and cnt[num]==1: ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)
#amax = 10**6

cnt = [0 for i in range(amax+1)]
for num in a:
    for i in range(1,amax//num + 1):
        tmp = num * i
        cnt[tmp] += 1

ans = 0
for num in a:
    if cnt[num]==1: ans += 1
print(ans)
n,l=map(int,input().split())

sum_ = 0
for i in range(n-1):
    sum_ = sum_ + (l + i - 1)

taste = [] 

for i in range(n):
    taste = sum_ - (l + i - 1)

min_sa = 0
sa = 0

for i in range(n):
    sa = sum_ - teste[i]
    if sa < min_sa:
        min_sa = sa

for i in range(n):
    if (sum_ - taste[i]) == min_sa:
        print(taste[i])
        break

### FIXED CODE ###

num = input()
#num = str(code)

if num[0] == num[1] or num[1] == num[2] or num[2] == num[3]:
    print('Bad')
else:
    print('Good')
N,M=map(int,input().split())
ab=[[0]*8]*8
a=[0]*M
b=[0]*M

reached=[0]*M

for i in range(M):
  a[i],b[i]=map(int,input().split())
  ab[a[i]-1][b[i]-1]=1
  ab[b[i]-1][a[i]-1]=1
    
def rootCount(pos,N,reached):
  count=0
  prev=0
  finish=1
  for i in range(N):
    if reached[i] == 0:
      finish=0
  if finish==1:
    return 1
    
  
  for i in range(1,N):
    if ab[pos][i]==0:
      continue
    if reached[i]==1:
      continue
    reached[i]=1
    count+=rootCount(i,N,reached)
    reached[i]=0
  return(count)

reached[0]=1
count=rootCount(0,N,reached)
print(count)


### FIXED CODE ###

from itertools import permutations
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
g=[[False]*N for i in range(N)]
for a,b in ab:
  g[a-1][b-1]=True
  g[b-1][a-1]=True
nodes=[i for i in range(1,N)]
ans=0
for route in permutations(nodes):
  if g[0][route[0]]== False:
    continue
  for i in range(N-1):
    if i == N-2:
      ans+=1
      
      break
    elif g[route[i]][route[i+1]]:
      continue
    else:
      break
print(ans)
import math
def lcm(n,m): return n*m//math.gcd(n,m)
A,B,C,D=map(int,input().split())
print(((B-A)-(((B-A)//C)+((B-A)//D)))+((B-A)//lcm(C,D)))

### FIXED CODE ###

N=list(input())
print('Yes' if '9' in N else 'No')
# coding: utf-8
import numpy as np
step_strings = {'L': 0, 'U': 1, 'D': 2, 'R': 3}
steps = input()
steps = np.array([step_strings[s] for s in steps])
steps_index = (np.arange(steps.size) + 1) % 2
if steps[steps_index == 0].max() < 3 and steps[steps_index == 1].min() > 0:
	print('Yes')
else:
  	print('No')

### FIXED CODE ###

# coding: utf-8
def is_easy(steps):
    for i, step in enumerate(steps):
        if i % 2 == 0 and step == 'L':
            return 'No'
        elif i % 2 == 1 and step == 'R':
            return 'No'
    return 'Yes'
  
steps = input()
print(is_easy(steps))
N, X = map(int, input().split())
L=list(map(int, input().split()))

D=0
count=1
while D<=X and count<=N+1:
   D=D+L[count-1]
   count+=1

print(min(N+1, count-1))

### FIXED CODE ###

N, X = map(int, input().split())
L=list(map(int, input().split()))

D=0
count=1
while D<=X and count<=N+1:
    if count != N+1:
       D=D+L[count-1] #count kaime no jump
    count+=1

print(count-1)
import sys
input=sys.stdin.readline

def is_prime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def make(n):
    ans=[]
    for i in range(2,n+1):
        if is_prime(i):
            ans.append(i)
    return ans

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    upper=max(Queries,key=lambda x:x[1])
    p_list=make(upper)

    for l,r in Queries:
        count=0
        for i in range(l,r+1,2):
            if i in p_list:
                if (i+1)//2 in p_list:
                    count+=1
        print(count)

### FIXED CODE ###

import sys
input=sys.stdin.readline

def Eratosthenes():
    num=[True for i in range(100001)]
    num[0]=False
    num[1]=False
    for i in range(2,100001):
        if num[i]:
            for j in range(2*i,100001,i):
                num[j]=False
    return num

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    p_list=Eratosthenes()
    dp=[0 for _ in range(100001)]
    for i in range(3,100000):
        if p_list[i] and p_list[(i+1)//2]:
            dp[i+1]=dp[i]+1
        else:
            dp[i+1] = dp[i]
    for l,r in Queries:
        print(dp[r+1]-dp[l])
n = int(input())
k = int(input())
ans = n - (k - 1)
print(ans)

### FIXED CODE ###

n, k = list(int(x) for x in input().split())

ans = 0

for i in range(1, n + 1):
    x = i + (k - 1)
    if x <= n:
        ans += 1

print(ans)
s=input()
if s[-1]==s:
	s1= s +"es"
  print(s1)
else:
  	s2 = s +"s"
    print(s2)

### FIXED CODE ###

s3="s"
es="es"
S=input()
if S[-1]=="s":
	s1= S + es
	print(s1)
else:
	s2 = S + s3
	print(s2)
N = int(input())
L = list(map(int, int(input())))
L.sort()
if L[-1] > (sum(L) - L[-1]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
if L[-1] < (sum(L) - L[-1]):
    print("Yes")
else:
    print("No")
N, M = map(int, input().split())
A = list(map(int, input().split()))

total_votes_checker = lambda M, i, total_votes: (False if i <= (1 / (4 * M)) * total_votes else True)

A = list(filter(lambda i: total_votes_checker(M, i, total_votes), A))

print("Yes") if len(A) >= M else print("No")



### FIXED CODE ###

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

total_votes = sum(A)

total_votes_checker = lambda M, i, total_votes: (False if i < (1 / (4 * M)) * total_votes else True)

A = list(filter(lambda i: total_votes_checker(M, i, total_votes), A))

print("Yes") if len(A) >= M else print("No")