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

#!/usr/bin/env python
"""M-SOLUTIONS プロコンオープン 2020: C - Marks
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_c
"""


def main():
    N, K = list(map(int, input().split()))
    As = list(map(int, input().split()))

    # N, K = [3, 2]
    # As = [1001, 869120, 1001]

    # N, K = [15, 7]
    # As = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
    prev_score = 0
    for i in range(N-(K-1)):
        # print('i:{}({})'.format(i, i+K))
        score = 1
        e = i + (K-1)
        s = i + ((K-1)-(K-1))
        # print('  {} => {}'.format(s, e+1))
        for j in range(s, e+1):
            score *= As[j]
        # print('score:{}'.format(score))
        # print('prev_score:{}'.format(prev_score))
        if prev_score == 0:
            prev_score = score
        else:
            # print('{} => {}'.format(prev_score, score))
            if prev_score < score:
                print('Yes')
            else:
                print('No')
            prev_score = score


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
"""M-SOLUTIONS プロコンオープン 2020: C - Marks
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_c
"""


def main():
    N, K = list(map(int, input().split()))
    As = list(map(int, input().split()))

    # N, K = [5, 3]
    # As = [96, 98, 95, 100, 20]

    # N, K = [3, 2]
    # As = [1001, 869120, 1001]

    # N, K = [15, 7]
    # As = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
    for i in range(0, N-K):
        # print('i:{}({})'.format(i, i+K))
        prev_score = As[i]
        score = As[K + i]
        # print('{} => {}'.format(prev_score, score))
        if prev_score < score:
            print('Yes')
        else:
            print('No')


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

def main(S=None):
    if not S:
        S = input()
    r = {k: 0 for k in range(0, 2019)}
    r[0] = 1
    tmp = 0
    base = 1
    for i, s in enumerate(S[::-1]):
        s = int(s) * base
        base *= 10
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for k, v in r.items():
        # if v > 1:
        #     print(k, v)
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    # assert main("1817181712114") == 3
    # assert main("14282668646") == 2
    # assert main("2119") == 0
    main()


### FIXED CODE ###

def main(S=None):
    if not S:
        S = input()
    r = [0]*2019
    r[0] = 1
    tmp = 0
    base = 1
    for s in S[::-1]:
        s = int(s) * base
        base *= 10
        base %= 2019
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for v in r:
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    # assert main("1817181712114") == 3
    # assert main("14282668646") == 2
    # assert main("2119") == 0
    main()
### BUGGY CODE ###

from collections import defaultdict


def longest_common_subsequence(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[-1][-1]


def main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence(X, Y))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict


def longest_common_subsequence(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[-1][-1]


def longest_common_subsequence2(s, t):
    dp = [0] * (len(t) + 1)
    for i in range(len(s)):
        si = s[i]
        tmp = dp[:]
        for j in range(len(t)):
            if si == t[j]:
                dp[j + 1] = tmp[j] + 1
            elif dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]
    return dp[-1]


def main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence2(X, Y))


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

N,K=list(map(int,input().split()))
p=list(map(int,input().split()))
counter=0
ans=0
for i in range(len(p)-K+1):
    count=0
    for j in range(K):
        count+=p[i+j]
    if counter<=count:
        counter=count
        ans=i
p2=[]
for i in range(K):
    p2.append(p[ans+i])
p3=[]
from itertools import accumulate
for i in p2:
    p3.append((sum(range(1,i+1))/i))
print(sum(p3))

### FIXED CODE ###

from itertools import accumulate
from collections import deque
N,K=list(map(int,input().split()))
p=list(map(int,input().split()))
p2=list(accumulate(p))
p2=deque(p2)
p2.appendleft(0)
p3=[]
ans=0
counter=0
ans2=0
for i in range(N-K+1):
    if counter<p2[i+K]-p2[i]:
        counter=p2[i+K]-p2[i]
        ans=i
for i in range(K):
    ans2+=sum(list(range(1,p[ans+i]+1)))/p[ans+i]
    
print(ans2)
### BUGGY CODE ###

import math
import bisect
import heapq
from collections import deque

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

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

d = [float('inf')] * n
d[0] = 0

for j in range(1, n):
    p = [d[i] + abs(h[j] - h[i]) for i in range(max(0, j - k), j)]

    d[j] = min(p)

print(d[n - 1])


### FIXED CODE ###

# import math
# import bisect
# import heapq
# from collections import deque

def main():
    n, k = map(int, input().split())

    h = list(map(int, input().split()))
    inf = 10**7
    d = [inf] * n
    d[0] = 0

    for j in range(1, n):
        p = [d[i] + abs(h[j] - h[i]) for i in range(max(0, j - k), j)]

        d[j] = min(p)

    print(d[-1])

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

def resolve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    A = []
    B = []
    ans = 0
    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a-1)
        B.append(b-1)
    while len(set(H)) != 0:
        v = H.index(max(H))+1
        for i in range(M):
            if A[i] == v:
                H[B[i]-1] = 0
            if B[i] == v:
                H[A[i]-1] = 0
        H[v-1] = 0
        ans += 1
    print(ans)
resolve()

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
count = [0]*N
ans = 0
for _ in range(M):
    a, b = map(int, input().split())
    if H[a-1] > count[b-1]:
        count[b-1] = H[a-1]
    if H[b-1] > count[a-1]:
        count[a-1] = H[b-1]
for i in range(N):
    if H[i] > count[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

mod = 10**9 + 7
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    primes = []
    isprime = [True for i in range(1001)]
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)
            for j in range(i * i, 1001, i):
                isprime[j] = False
    x = a[0]
    f = True

    cnt = [0 for i in range(1000001)]
    for val in a:
        x = gcd(x, val)
        i = 0
        tmp_val = val
        while i < len(primes) and primes[i] ** 2 <= tmp_val:
            if val % primes[i] == 0:
                cnt[primes[i]] += 1
                while val % primes[i] == 0:
                    val //= primes[i]
            i += 1
        if val > 1:
            cnt[val] += 1
    for i in range(2, 1000001):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print('pairwise coprime')
    elif x == 1:
        print('setwise coprime')
    else:
        print('not coprime')



t = 1
while t > 0:
    solve()
    t -= 1

### FIXED CODE ###

mod = 10**9 + 7
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    primes = []
    isprime = [True for i in range(1001)]
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)
            for j in range(i * i, 1001, i):
                isprime[j] = False
    x = a[0]
    f = True

    cnt = [0 for i in range(1000001)]
    for val in a:
        x = gcd(x, val)
        i = 0
        while i < len(primes) and primes[i] ** 2 <= val:
            if val % primes[i] == 0:
                cnt[primes[i]] += 1
                while val % primes[i] == 0:
                    val //= primes[i]
            i += 1
        if val > 1:
            cnt[val] += 1
    for i in range(2, 1000001):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print('pairwise coprime')
    elif x == 1:
        print('setwise coprime')
    else:
        print('not coprime')



t = 1
while t > 0:
    solve()
    t -= 1
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    while True:
      mid = (l+r)//2
      if a > 0:
        if r - l <=1:
          return r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return n - r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          r = mid
        else:
          l = mid

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      tot = 0
      for A in As:
        tot += count(-1, n, A, mid)
      tot //= 2
      if tot < k:
        l = mid
      else:
        r = mid
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while  r >= 0 and xs[l] * ys[r] > ub:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      
      tot = 0      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int, input().split()))
big = []
Max = 0
for i in range(N):
    Sum=0
    if i+K<=N:
        for j in range(K):
            Sum += p[i + j]
        if Sum > Max:
            Max = Sum
            index=i
for i in range(K):
    big.append(p[index+i])
ans = []
for i in big:
    kitai=0
    for j in range(1,i+1):
        kitai += j
    kitai = kitai / i
    ans.append(kitai)
print(sum(ans))

### FIXED CODE ###

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

s=[0]*(N+1)
for i in range(N):
    s[i + 1] = s[i] + p[i]

Max = 0
for i in range(N):
    Sum=0
    if i+K<=N:
        Sum = s[K+i] - s[i]
        if Sum > Max:
            Max = Sum
            index = i
    else:
        break
Sum=0
for i in range(K):
    kitai=1/2*p[index+i]*(p[index+i]+1)
    kitai = kitai / p[index+i]
    Sum+=kitai
print(Sum)
### BUGGY CODE ###

#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
R3=RollingHash(S,36,10**10+19)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln),R3.get(l,l+ln))
        if tmp in D:
            if D[tmp]+ln<=l:
                ans=max(ln,ans)
        else:
            D[tmp]=l
print(ans)


### FIXED CODE ###

#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln))
        if tmp in D:
            if D[tmp]+ln<=l:
                ans=max(ln,ans)
        else:
            D[tmp]=l
print(ans)
### BUGGY CODE ###

from math import factorial
import collections

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

COUNTS = collections.Counter(BALLS)


MEMO = {}
def fact(n):
    if MEMO.get(n):
        return MEMO[n]
    r = 2
    if n - r < 0:
        return 0
    MEMO[n] = factorial(n) // factorial(r) // factorial(n - r)
    return MEMO[n]

MEMO2 = {}
def solve(n):
    if MEMO2.get(n):
        return MEMO2[n]

    MEMO2[n] = sum(fact(v if k != n else v - 1) for (k, v) in COUNTS.items())
    return MEMO2[n]

for i in range(N):
    print(solve(BALLS[i]))

### FIXED CODE ###

from math import factorial
import collections

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

MEMO = {}
def fact(n):
    if MEMO.get(n):
        return MEMO[n]
    r = 2
    if n - r < 0:
        MEMO[n] = 0
        return 0
    MEMO[n] = factorial(n) // factorial(r) // factorial(n - r)
    return MEMO[n]

COUNTS = collections.Counter(BALLS)
TOTAL = sum(fact(n) for n in COUNTS.values())

MEMO2 = {}
def solve(n):
    if MEMO2.get(n):
        return MEMO2[n]

    MEMO2[n] = TOTAL - fact(COUNTS[n]) + fact(COUNTS[n] - 1)
    return MEMO2[n]

for i in range(N):
    print(solve(BALLS[i]))
### BUGGY CODE ###

s = input()
n = int(input())
for i in range(n):
    li = input().split()
    if(li[0] == '1'):
        s = s[::-1]
    else:
        if(li[1] == '1'):
            s = li[2] + s
        else:
            s = s + li[2]
print(s)

### FIXED CODE ###

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)
### BUGGY CODE ###

import heapq
from operator import itemgetter
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1), reverse=True)
for i in range(m):
  b, c = BC[i]
  for _ in range(b):
    t = heapq.heappop(A)
    heapq.heappush(A, max(c, t))
print(sum(A))

### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
A = [(1, i) for i in map(int, input().split())]
BC = [ tuple(map(int, input().split())) for _ in range(m) ]
XY = sorted(A + BC, reverse=True, key=itemgetter(1))
c = n
now = 0
ans = 0
while c > 0 and now < n+m:
  x, y = XY[now]
  t = min(c, x)
  ans += y*t
  c -= t
  now += 1
print(ans)
### BUGGY CODE ###

ans = input()
n = int(input())
for i in range(n):
    query = input()
    if query == "1":
        ans = ''.join(reversed(list(ans)))
    else:
        _,option,str = query.split()
        if option == "1":
            ans = str + ans
        else:
            ans += str
print(ans)

### FIXED CODE ###

from collections import deque

def main():
    ans = deque(input())
    n = int(input())
    vec = 1
    for i in range(n):
        q = input()
        if q == "1":
            vec *= -1
        else:
            _,o,s = q.split()
            if ((o == "1") and (vec == 1)) or ((o == "2") and (vec == -1)):
                ans.appendleft(s)
            else:
                ans.append(s)
    if vec == -1:
        ans.reverse()
    ans = ''.join(ans)
    print(ans)

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

import bisect
N = int(input())
A = []
for i in range(N):
    a = int(input())
    b = bisect.bisect_left(A,a)
    if b == 0:
        A.insert(0,a)
    else:
        A[b-1] = a
print(len(A))

### FIXED CODE ###

import bisect
N = int(input())
A = []
for i in range(N):
    a = int(input()) * (-1)
    b = bisect.bisect_right(A,a)
    if b == len(A):
        A.append(a)
    else:
        A[b] = a
print(len(A))
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
p = 0
for n in range(N):
  for m in range(n+1, N):
    p += X[n]*X[m]
  if p >= 10**9 + 7:
    while p >= 10**9 + 7:
      p -= 10**9 + 7
      
print(p)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
p = 0
s = sum(X)
for n in range(N):
  s -= X[n] 
  s = s % (10**9 + 7)
  p += s * X[n]
  p = p % (10**9 + 7)

print(p)
### BUGGY CODE ###

input_list = list(map(int, input().split()))
count = input_list[0]
y = input_list[1]

from math import floor

l_lim = floor(y / 10000)
m_lim = floor(y / 5000)
n_lim = floor(y / 1000)

flag = False
for l in range(l_lim + 1):
    for m in range(m_lim + 1):
        for n in range(n_lim + 1):
            if (l+m+n == count)&(10000 * l + 5000 * m + 1000 * n == y):
                print(l, m, n)
                flag = True
                break
        if flag:
            break
    if flag:
        break
if flag == False:
    print(-1, -1, -1)

### FIXED CODE ###

input_list = list(map(int, input().split()))
count = input_list[0]
y = input_list[1]
flag = False
for l in range(count + 1):
    for m in range(count - l + 1):
        n = count - l - m
        if 10000 * l + 5000 * m + 1000 * n == y:
            print(l, m, n)
            flag = True
            break
        if flag:
            break
    if flag:
        break
if flag == False:
    print(-1, -1, -1)
### BUGGY CODE ###

n=int(input())
A = list(map(int,input().split()))
for i in range(1,n+1):
    print(A.count(i))

### FIXED CODE ###

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

def main():
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  a.sort(reverse=True)
  hi = -1
  lo = n
  while lo-hi>1:
    mid = (lo+hi)//2
    if a[mid] >= k:
      hi = mid
    else:
      lo = mid
  ng = hi
  ok = n
  while ok-ng > 1:
    mid = (ok+ng)//2
    dp = [False]*(k+1)
    dp[0] = True
    for j in range(n):
      if j == mid:
        continue
      w = a[j]
      for i in range(k,w-1,-1):
        dp[i] |= dp[i-w]
    if any(dp[k-a[mid]:k]):
      ng = mid
    else:
      ok = mid
  print(n-ok)
  return
if __name__ == "__main__":
  main()

### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
### BUGGY CODE ###

N = int(input())
S = input()

ans_list = {}

for i in range(N):
    for j in range(i+1, N):
        if not S[j + 1:N]:
            continue
        elif S[i] + S[j] not in ans_list:
            ans_list[S[i] + S[j]] = list(S[j + 1:N])
        else:
            ans_list[S[i] + S[j]].extend(list(S[j+1:N]))
count = 0
# print(ans_list)
for v in ans_list.values():
    # print(v)
    count += len(set(v))
print(count)

### FIXED CODE ###

N = int(input())
S = list(input())
visited = {}

count = 0

for i, s in enumerate(S):
    if s in visited:
        continue
    visited[s] = []
    for j, s2 in enumerate(S[i+1:N-1]):
        # print(s, s2, S[i + j + 2:N])
        if s2 in visited[s]:
            continue
        count += len(set(S[i + j + 2:N]))
        visited[s].append(s2)
        # print(s, s2, set(S[j + 1:N]))
print(count)
### BUGGY CODE ###

import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2:
        return False
    # 2は素数
    elif num == 2:
        return True
    # 偶数は素数ではない
    elif num % 2 == 0:
        return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = set()
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.add(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
# print(callIsPrime(10**5))

sosuu = callIsPrime(10**5)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    count = 0
    for i in range(l, r+1, 2):
        # print(i)
        if i in sosuu and (i+1)//2 in sosuu:
            count += 1
    print(count)

### FIXED CODE ###

import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2:
        return False
    # 2は素数
    elif num == 2:
        return True
    # 偶数は素数ではない
    elif num % 2 == 0:
        return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = set()
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.add(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
# print(callIsPrime(10**5))

sosuu = callIsPrime(10**5)
count_dic = {}
count = 0
for i in range(1, 10**5, 2):
    if i in sosuu and (i+1)//2 in sosuu:
        count += 1
    count_dic[i] = count
# print(count_dic)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    # if r == l:
    #     print(count_dic[r]-count_dic[l]+1)
    # else:
    print(count_dic[r] - count_dic[max(l-2, 1)])