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

import sys
sys.setrecursionlimit(10**6)

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

ans = 1000

def dfs(money, share, day):
    global ans
    if day > n:
        ans = max(ans, money)
        return
    max_buy = money//A[day-1]
    max_sel = share
    for n_buy in range(-max_sel, max_buy+1):
        dfs(money-n_buy*A[day-1], share+n_buy, day+1)

dfs(1000,0,1)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

CurrentMoney = 1000

for i in range(0, n-1):
    Stocks = 0
    if A[i] < A[i+1]: Stocks = CurrentMoney // A[i]
    CurrentMoney += (A[i+1] - A[i]) * Stocks

print(CurrentMoney)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = []
for i in range(m):
    a.append(int(input()))
dp = [0 for _ in range(n+1)]
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, n+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 2] + dp[i - 1]
print(dp[n] % 1000000007)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = []
for i in range(m):
    a.append(int(input()))
a = set(a)
dp = [0 for _ in range(n+1)]
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, n+1):
    if not(i in a):
        dp[i] = dp[i - 2] + dp[i - 1]
print(dp[n] % 1000000007)
### BUGGY CODE ###

N = int(raw_input())

i, j = 1, 1
footsteps = []
while i * j != N:
    footsteps.append((i, j))
    left = (i - 1) * j
    up = i * (j - 1)
    right = (i + 1) * j
    down = i * (j + 1)
    distances = {
            (i - 1, j): abs(N - left),
            (i, j - 1): abs(N - up),
            (i + 1, j): abs(N - right),
            (i, j + 1): abs(N - down),
            }
    items = distances.items()
    items = filter(lambda (k, v): k not in footsteps, items)
    i, j = min(items, key=lambda (k, v): v)[0]
print i - 1 + j - 1


### FIXED CODE ###

import math

N = int(raw_input())

limit = int(math.sqrt(N)) + 1
n = float(N)
minimum = (1, 1, N)
for i in range(1, limit):
    j = n / i
    if not j.is_integer():
        continue
    j = int(j)
    distance = i + j - 2
    if minimum[2] > distance:
        minimum = i, j, distance
print(minimum[2])
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
m = len(bin(max(A)))-2
zero = [0]*m
one = [0]*m
for a in A:
  for i in range(m):
    zero[i] += 1-(a>>i)&1
    one[i] += (a>>i)&1
ans = 0
for i in range(m):
  ans = (ans+zero[i]*one[i]*2**i)%mod
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())))
mod = 10**9+7
m = len(bin(max(A)))-2
ans = 0

for i in range(m):
  one = np.count_nonzero((A >> i)&1)
  zero = n - one
  ans += (pow(2,i,mod)*zero*one)%mod
print(ans%mod)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    dpn = [0]*13
    keta = 1
    zero = 0
    # print(dp)
    for c in reversed(S):
        if c == "?":
            dpn = [0]*13
            for i in range(10):
                for j in range(13):
                    dpn[j] += dp[(j - i*keta) % 13]
                    dpn[j] %= MOD
            dp = dpn
        else:
            shift = (int(c)*keta) % 13
            dpn = [0]*13
            for i in range(13):
                dpn[i] = dp[(i-shift) % 13]
            # dpn = dp[13-shift:]+dp[:13-shift]
            dp = dpn

        # print(c, dp)
        keta *= 10
        keta %= 13

    print(dp[5])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    dpn = [0]*13
    keta = 1
    zero = 0
    # print(dp)
    for c in reversed(S):
        if c == "?":
            dpn = [0]*13
            for i in range(10):
                for j in range(13):
                    dpn[j] += dp[(j - i*keta) % 13]
                    dpn[j] %= MOD
            dp = dpn
        else:
            shift = (int(c)*keta) % 13
            dpn = [0]*13
            for i in range(13):
                dpn[i] = dp[(i-shift) % 13]
            # dpn = dp[13-shift:]+dp[:13-shift]
            dp = dpn

        # print(c, dp)
        keta *= 10
        keta %= 13

    print(dp[5])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


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

N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp = [[False]*K for _ in range(2)]
    dp[0][0] = True
    for i in range(N-1):
        for j in range(K):
            if j < L[i]:
                dp[(i+1)%2][j] = dp[i%2][j]
                continue
            dp[(i+1)%2][j] = dp[i%2][j] | dp[i%2][j-L[i]]
        
    res = False
    for j in range(K-A[n], K):
        if dp[(N+1)%2][j]:
            res = True
            break
            
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)

### FIXED CODE ###

N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()
for i in range(N):
    if A[i] >= K:
        A = A[:i]
        break

N = len(A)

def f(n): #aiが必要か不必要か判定
    dp = [0]*K
    dp[0] = 1
    for i in range(N):
        if i == n:
            continue
        for j in range(K-1, A[i]-1, -1):
            dp[j] |= dp[j-A[i]]
            
    res = False
    for j in range(K-A[n], K):
        if dp[j]:
            res = True
            break
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)
### BUGGY CODE ###

import numpy as np
X = [int(x) for x in input().split()]
list.sort(X,reverse=True)
A,B,C = X[0],X[1],X[2]
count = 0

while A!=B or B!=C or C!=A:
    if (B-C)%2 == 1:
        A=A+1
        B=B+1
        count = count + 1
    
    elif B!=C and (B-C)%2 == 0:
        while B!=C and B < A and C < A:
            C = C + 2
            count = count + 1
    else:
        B = B + 1
        C = C + 1
        count = count + 1

print(count)


### FIXED CODE ###

X = [int(x) for x in input().split()]
list.sort(X,reverse=True)
A,B,C = X[0],X[1],X[2]
count = 0

while A!=B or B!=C or C!=A:
    if (B-C)%2 == 1 and A==B:
        A=A+1
        B=B+1
        count = count + 1
    elif B!=C and (B-C)%2 == 0:
        while B!=C:
            C = C + 2
            count = count + 1
    else:
        B = B + 1
        C = C + 1
        count = count + 1

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

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def f(a, s, n):
    if s[-1] == "1":
        return 1

    s0 = "0"
    st = {0,}
    aa = [st]
    for ai, si in zip(a, s):
        if s0 == si:
            tmp = [x^ai for x in st]
            st.update(tmp)
        else:
            st = {0, ai,}
            aa.append(st)
            s0 = si

    a3 = set()
    for i in range(len(aa)-1, 0, -2):
        a0, a1 = aa[i], aa[i-1]
        a0 |= a3
        if a1 <= a0:
            a3 = a0 - a1
        else:
            return 1
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

X = (10**18).bit_length()

def f(a, s, n):
    if s[-1] == "1":
        return 1

    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


def resolve():
    T = int(input())

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

    print(*ans, sep="\n")

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

n = int(input())
List = list(map(int, input().split()))
flag = True

for i in range(n):
    if flag:
        obj = List[i]
        for j in range(i+1, n - i):
            if obj == List[j]:
                flag = False
        
if flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

def ha(st):
    return len(st) != len(set(st))

if ha(List):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

answer = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    if r*R + g*G > N or (N-r*R-g*G)%B != 0:
      continue
    else:
      answer += 1
print(answer)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

answer = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    if r*R + g*G > N:
      break
    elif (N-r*R-g*G)%B != 0:
      continue
    else:
      answer += 1
print(answer)
### BUGGY CODE ###

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

minc = 100000000

for i in range(len(s)):
  left_wrong = s[0:i].count('W')
  right_wrong = s[i:].count('E')
  minc = min(minc,(left_wrong+right_wrong))

print(minc)


### FIXED CODE ###

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

nums = [s[1:].count('E')]
for i in range(1,n):
  tmp = nums[i-1]
  if s[i-1] == 'W':
    tmp  += 1
  if s[i] == 'E':
    tmp -= 1
  nums.append(tmp)

print(min(nums))
### BUGGY CODE ###

from collections import deque
import sys
from collections import defaultdict
input = sys.stdin.readline
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]

INF = 10 ** 9
n = H * W
d =[[float("inf") for _ in range(n)] for _ in range(n)]
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for x in range(W):
    for y in range(H):
        for temp in go:
            gx,gy = temp
            nx = x + gx
            ny = y + gy
            if 0<= nx < W and 0<= ny < H and C[ny][nx] != "#":
                d[ny * W + nx][y * W + x] = 1
                d[y * W + x] [ny * W + nx]= 1
for i in range(n):
    d[i][i] = 0
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if C[i//W][i%W] != "#" and C[j//W][j%W] != "#" and C[k//W][k%W] != "#":
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
ans = warshall_floyd(d)
# print(ans)
x  = 0
for temp in ans:
    for k in temp:
        if k != float("inf"):
            x = max(k,x)
print(x)



### FIXED CODE ###

from collections import deque
import sys
from collections import defaultdict
input = sys.stdin.readline



H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1
for sx in range(W):
    for sy in range(H): # スタート地点のループ
        if C[sy][sx] == "#":
            continue
        
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for temp in go:
                gx,gy = temp
                nx = x + gx
                ny = y + gy
                if 0<= nx < W and 0<= ny < H and C[ny][nx] != "#":
                    if dist[ny][nx] == -1: # ここの更新にminはいらない(幅優先なので自明に最短距離を進む)
                        dist[ny][nx] = dist[y][x] + 1
                        que.append( (ny,nx))
        for temp in dist:
            cand = max(temp)
            ans = max(ans,cand)
print(ans)
### BUGGY CODE ###

S = input()

count = 0
mod_check = {}
mod_check[0] = 1
for x in range(len(S) - 1, -1, -1):
    check_S = int(S[x:])
    mod = check_S % 2019
    mod_check.setdefault(mod, 0)
    mod_check[mod] += 1
mod_match = 0
for x in mod_check.values():
    mod_match += x * (x - 1) // 2
print(mod_match)


### FIXED CODE ###

S = input()

count = 0
mod_check = [0] * 2019
mod_check[0] = 1
check_S = 0
d = 1
for i in reversed(S):
    check_S += int(i) * d
    check_S %= 2019
    mod_check[check_S] += 1
    d *= 10
    d %= 2019
    count += 1
mod_match = 0
for x in mod_check:
    mod_match += x * (x - 1) // 2
print(mod_match)
### BUGGY CODE ###

A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1

for n in range(1, l):
    S += (int(A[-n])*(10**(n-1)))
    sm = S % 2019
    lis[sm] += 1

result = 0

for n in lis:
    result += (n*(n-1)/2)


print(int(result))


### FIXED CODE ###

S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
### BUGGY CODE ###

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

max = max(a)
min = max * -1
ans = 10000000
prev = 10000000
t = len(a)
flag = 0
for b in range(min,max):
  sum = 0
  for i in range(t):
    sum += abs(a[i] - (b+i+1))
  if ans > sum:
    ans = sum
  if prev < sum:
    flag += 1
  if flag == 2:
    break
  prev = sum

print(ans)

### FIXED CODE ###

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

b = []

for i in range(n):
  b.append(a[i]-(i+1))

# print(b)
b.sort()
# print(b)

min_b=b[n//2]
# print(min_b)

ans = 0
for i in range(n):
  ans+=abs(a[i]-(min_b+(i+1)))
  # print(ans)
print(ans)
### BUGGY CODE ###

a=raw_input()
b=raw_input()
if len(a)<len(b):
	print "LESS"
elif len(a)>len(b):
	print "GREATER"
else:
	p=0
	flag=True
	while flag:
		if a[p]<b[p]:
			print "LESS"
			flag=False
		elif a[p]>b[p]:
			print "GREATER"
			flag=False
		else:
			pass


### FIXED CODE ###

a=int(raw_input())
b=int(raw_input())
if a<b:
	print "LESS"
elif a>b:
	print "GREATER"
else:
	print "EQUAL"
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

mod = 10**9 + 7

res = 0

for i in range(60):
    count = 0
    for j in range(N):
        if ((A[j] >> i) & 1):
            count += 1
    res += (N - count) * count * 2 ** i 
    res %= mod

print(res)


### FIXED CODE ###

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

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

A = np.array(A,np.int64)

mod = 10**9 + 7

res = 0

for i in range(60):
    count = np.count_nonzero(A & 1)
    res += (N - count) * count * 2 ** i
    res %= mod
    A >>= 1

print(res)
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[[0 if ((i==0) and (j==0) and (k==0)) else N/(i+j+k) for k in range(C+1)] for i in range(B+C+1)] for j in range(A+B+C+1)]

    for k in range(C+1):
        for j in range(E+1):
            for i in range(N+1):
                if (i==0) and (j==0) and (k==0):
                    continue
                d = dp[i][j][k]
                if (i<N):
                    dp[i+1][j][k] += (i+1)*d/(i+1+j+k)
                if (i>0) and (j<E):
                    dp[i-1][j+1][k] += (j+1)*d/(i+j+k)
                if (j>0) and (k<C):
                    dp[i][j-1][k+1] += (k+1)*d/(i+j+k)

    print(dp[A][B][C])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

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

def popcount(n):
    count = 0
    while n > 0:
        if n % 2 == 1:
            count += 1
        n //= 2
    return count


N = int(input())
X = input()

X_int = int(X, 2)

for i in range(N):
    mask = 2**(N-i-1)
    Xi = X_int ^ mask

    n = Xi
    ans = 0
    while n > 0:
        ans += 1
        n %= popcount(n)
    print(ans)

### FIXED CODE ###

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()
### BUGGY CODE ###

import re

int(input())
u = input()
l = []
res = 0


def remove_ad(li):
    li2 = ""
    q = ""
    r = ""
    s = ""
    for p in str(li):
        if (p != q):
            li2 = li2 + p
        else:
            if (p != r):
                li2 = li2 + p
            else:
                if (p != s): li2 = li2 + p
        s = r
        r = q
        q = p
    return(li2)



t = remove_ad(u)
n = len(t)

for i in range(0,n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if(t[i]+t[j]+t[k] not in l):
                l.append(t[i]+t[j]+t[k])
                res += 1

print(res)

### FIXED CODE ###

from itertools import product

N = int(input())
S = input()
S = [int(s) for s in S]


res = 0
for q in product(range(10), repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                res += 1
                break
            else:
                i+=1
print (res)
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    MOD = 10 ** 9 + 7
    S = sr()
    # 桁DP, 上から
    dp = [[0] * 13 for _ in range(2)]
    dp[0][0] = 1
    for i in range(len(S)):
        num = S[i]
        i %= 2
        if num.isdigit():
            num = int(num)
            for j in range(13):
                dp[1-i][(10*j+num)%13] = dp[i][j]
        else:
            dp[1-i] = [0] * 13
            for j in range(13):
                for k in range(10):
                    dp[1-i][(10*j+k)%13] += dp[i][j]
                dp[1-i][j] %= MOD

    answer = dp[len(S)%2][5]
    print(answer%MOD)

if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
cnt = 0
nr = n // r
ng = n // g
for i in range(nr + 1):
    for j in range(ng + 1):
        tmp = n - i * r - j * g
        if tmp >= 0 and tmp % b == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i * r + j * g == n:
            ans += 1
        elif (n - (i * r + j * g)) >= 0 and (n - (i * r + j * g)) % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = dpi[j] + 1
      else:
        if dpi1[j] > dpi[j1]:
          dpi1[j1] = dpi1[j]
        else:
          dpi1[j1] = dpi[j1]
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

# https://abc084.contest.atcoder.jp/tasks/abc084_d

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True


def main():
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    p_l = [i for i in range(2, 10**5 + 1) if is_prime(i)]

    for lr in lrs:
        ans = 0
        for i in range(lr[0], lr[1] + 1, 2):
            ans += 1 if i in p_l and (i + 1) // 2 in p_l else 0
        print(ans)


main()






### FIXED CODE ###

# https://abc084.contest.atcoder.jp/tasks/abc084_d


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime


def main():
    p_l = primes(10**5)
    total = [0 for _ in range(10 ** 5 + 1)]
    for i in range(3, 10 ** 5 + 1):
        if p_l[i] and p_l[(i + 1) // 2]:
            total[i] = 1 + total[i - 1]
        else:
            total[i] = total[i - 1]

    # print(total[:10])
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    for lr in lrs:
        print(total[lr[1]] - total[lr[0]-1])


main()