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

from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]
gids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, gids
    queue = deque()
    queue.append(s)
    visited = [0] * n
    visited[s] = 1
    gids[s] = gid

    while queue:
        i = queue.popleft()
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                gids[f] = gid
                queue.append(f)


gid = 1
for i in range(n):
    if gids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = gids[s], gids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
### BUGGY CODE ###

def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(W+1)[::-1]:
            if w<=i:
                can1=dp[i-w]+v
                can2=dp[i]
                dp[i]=max(can1,can2)
            else:
                break
    print(max(dp))
main()

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

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

# abc123_d
import itertools
import math

# input
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# getans
arr = itertools.product(A, B)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)[:K]
C = sorted(C, reverse=True)[:K]
arr = itertools.product(arr, C)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)[:K]
# output
for a in arr:
    print(a)



### FIXED CODE ###

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

# abc123_d
import itertools
import math

# input
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# A = range(1000)
# B = range(1000)
# C = range(1000)
# getans
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
arr = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            arr.append(A[i]+B[j]+C[k])
#print(len(arr))
arr.sort(reverse=True)
# output
ans = '\n'.join(map(str, arr[:K]))
print(ans)
### BUGGY CODE ###

import bisect
import itertools

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

RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
RGB.sort(key=lambda x:len(x))
len_B=len(RGB[2])
max_B=max(RGB[2])
min_B=min(RGB[2])
#for r in RGB[0]:
#    for g in RGB[1]:
for rg in itertools.product(RGB[0],RGB[1]):
    r=rg[0]
    g=rg[1]
    dif = abs(r - g)

    up = max(r,g)+dif
    down = min(r,g)-dif
    if max_B >=up:
        if RGB[2][bisect.bisect_left(RGB[2],up)]==up:
            total-=1
    if min_B <= down and max_B >= down:
        if RGB[2][bisect.bisect_left(RGB[2],down)]==down:
            total-=1
    if dif % 2 == 0:
        center = (r+g)/2
        center_posi=bisect.bisect_left(RGB[2], center)
        if center_posi < len_B:
            if RGB[2][center_posi]==center:
                total-=1
print(total)

### FIXED CODE ###

import bisect
import itertools

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

RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
RGB.sort(key=lambda x:len(x))
len_B=len(RGB[2])
max_B=max(RGB[2])
min_B=min(RGB[2])
#for r in RGB[0]:
#    for g in RGB[1]:
bool_B=[False for i in range(n)]
for i in RGB[2]:
    bool_B[i]=True

for rg in itertools.product(RGB[0],RGB[1]):
    r=rg[0]
    g=rg[1]
    dif = abs(r - g)

    up = max(r,g)+dif
    down = min(r,g)-dif

    if max_B >=up:
        if bool_B[up]:
            total-=1
    if min_B <= down and max_B >= down:
        if bool_B[down]:
            total-=1
    if dif % 2 == 0:
        center = (r+g)//2
        if min_B<=center and max_B >= center:
            if bool_B[center]:
                total-=1
print(total)
### BUGGY CODE ###

from functools import reduce
import math

N = int(input())
gcds = []
num = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            gcds.append(reduce(math.gcd,[i,j,k]))

print(sum(gcds))

### FIXED CODE ###

from math import gcd

K = int(input())

memo = []
memolist = []
for i in range(1,K+1):
    if i != 1:
        memo.append(memolist)
    memolist = []
    for j in range(1,K+1):
        memolist.append(gcd(i,j))
memo.append(memolist)

result = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            result += gcd(memo[i-1][j-1],k)

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

n = int(input())
l = list(map(int,input().split()))
mod = 10**9+7
if n % 2 == 1:
    for i in range(1,n//2+1):
        if l.count(2*i) != 2:
            print(0)
            exit()
    print(pow(2,n//2,mod))
else:
    for i in range(n//2):
        if l.count(2*i+1) != 2:
            print(0)
            exit()
    print(pow(2,n//2,mod))


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
mod = 10**9+7
if n % 2 == 1:
    if l[0] != 0:
        print(0)
        exit()
    count = 2
    for i in range(1,n-1,2):
        
        if l[i] != count or l[i] != l[i+1]:
            print(0)
            exit()
        count += 2
    print(pow(2,n//2,mod))
else:
    count = 1
    for i in range(0,n-1,2):
        if l[i] != count or l[i] != l[i+1]:
            print(0)
            exit()
        count += 2
    print(pow(2,n//2,mod))
### BUGGY CODE ###

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


c = 0

for i in range(a):
    if (b[i]-1)*(a-i)>=sum(b[i:a]):
      c+=1
      break
if c==0: print("Yes")
else: print("No")

### FIXED CODE ###

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

c = 0

for i in range(a):
  if i>0:
    if (b[i] - b[i-1])<-1:
      c+=2
    if (b[i] - b[i-1])==-1:
      c+=1
    if (b[i] - b[i-1])>0:
      c=0
  if c>=2: break
if c<=1: print("Yes")
else: print("No")
### BUGGY CODE ###

N = int(input())
l = input().split(" ")
P = [int(n) for n in l]

# i=1は必ずOK
c = 1

for i in range(1,N):
  n_i = P[i]
  p = P[:i+1]
  
  for j in range(i+1):
    if p[j] < n_i:
      break
      
  if j==i:
    c+=1
    
print(c)

### FIXED CODE ###

N = int(input())
l = input().split(" ")
P = [int(n) for n in l]

# i=1は必ずOK
c = 1
min = P[0]

for i in range(1,N):
  p = P[i]
  if p<=min:
    c+=1
    min=p
    
print(c)
### BUGGY CODE ###

import functools
import fractions

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

gcd_all = functools.reduce(fractions.gcd, A)

for i in range(N):
    gcd_1 = functools.reduce(fractions.gcd, (A[:i]+A[i+1:]))
    if gcd_1 >= gcd_all:
        gcd_all = gcd_1

print(gcd_all)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC132 C

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

ans = 0
for i in range(min(d),max(d)):
    s = 0
    t = 0
    for j in range(N):
        if d[j] <= i:
            s += 1
        else:
            t += 1
        if s > N//2:
            break
        if t > N//2:
            break
    if s == t:
        ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC132 C
import sys
sys.setrecursionlimit(1000000)
from collections import deque

N = int(input())
d = list(map(int,input().split()))
d.sort()
if N % 2 == 0:
    print(d[N//2]-d[N//2-1])
else:
    print(0)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
CB = deque([])
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB = sorted(CB, reverse=True)
flag = False
for i in CB:
    if flag:
        break
    c = 0
    while c < i[1]:
        if i[0] > A[c]:
            A[c] = i[0]
            c += 1
        else:
            c = i[1]
            flag = True
    A = sorted(A)
print(sum(A))

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
CB = deque([])
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB = sorted(CB, reverse=True)
flag = False
c = 0
I = 0
for i in CB:
    I += i[1]
    if flag:
        break
    while c < I:
        if c >= N:
            break
        if A[c] < i[0]:
            A[c] = i[0]
            c += 1
        else:
            c = I
            flag = True
print(sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for i in range(N)]

    temp = 0
    minimum = -1
    for i in range(N):
        temp = A[i]
        A[i] = minimum
        print(max(A))
        A[i] = temp


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    A_sorted = sorted(A)

    for i in range(N):
        if A_sorted[-1] == A[i]:
            print(A_sorted[-2])
        else:
            print(A_sorted[-1])


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

# -*- coding: utf-8 -*-
import math

# def f2(x, y, z, n):
#     return x*x+y*y+z*z+x*y+y*z+z*x

def f(x, y, z, n):
    if x*x+y*y+z*z+x*y+y*z+z*x == n:
        return True
    else:
        return False
def main():
    N = int(input())
    for n in range(1, N + 1):
        cnt = 0
        for x in range(1, 100):
            if x * x > n:
                break
            for y in range(x, 100):
                if x*x + y*y > n:
                    break
                for z in range(y, 100):
                    if x*x + y*y + z*z > n:
                        break
                    if f(x, y, z, n):
                        # print(x, end=' ')
                        # print(y, end=' ')
                        # print(z)
                        if x == y == z:
                            cnt += 1
                        elif x != y and y != z and z != x:
                            cnt += 6
                        else:
                            cnt += 3
        # print(n, end=': ')
        print(cnt)
    return
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

# def f2(x, y, z, n):
#     return x*x+y*y+z*z+x*y+y*z+z*x

def f(x, y, z, n):
    if x*x+y*y+z*z+x*y+y*z+z*x == n:
        return True
    else:
        return False
def main():
    N = int(input())
    for n in range(1, N + 1):
        cnt = 0
        for x in range(1, 100):
            if x * x > n:
                break
            for y in range(x, 100):
                if x*x + y*y > n:
                    break
                for z in range(y, 100):
                    if x*x + y*y + z*z > n:
                        break
                    if f(x, y, z, n):
                        # print(x, end=' ')
                        # print(y, end=' ')
                        # print(z)
                        if x == y == z:
                            cnt += 1
                        elif x != y and y != z and z != x:
                            cnt += 6
                        else:
                            cnt += 3
        # print(n, end=': ')
        print(cnt)
    return
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m = map(int, input().split())
spotwork = []
for i in range(n):
    spotwork.append(list(map(int, input().split())))

spotwork.sort(key=lambda x: x[1], reverse=True)
#print(spotwork)

shift = [0] * m
for i in range(n):
    delay, payment = spotwork[i]
    for day in range(m - delay, -1, -1):
        if shift[day] == 0:
            shift[day] = payment
            break
print(sum(shift))

### FIXED CODE ###

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

Work = []
for i in range(n):
    Work.append(list(map(int, input().split())))
Work.sort(key=lambda x: (x[0], x[1]), reverse=True)
#print(Work)

total = 0
job_stock = []
#-1をかけた値を格納
heapq.heapify(job_stock)
for day in range(m, -1, -1):
    allowed_delay = m - day
    try:
        while Work[-1][0] <= allowed_delay:
            delay, money = Work.pop()
            heapq.heappush(job_stock, -money)
    except:
        pass
    if len(job_stock) >= 1:
        job_today = -heapq.heappop(job_stock)
        total += job_today
print(total)
### BUGGY CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
dp = [[{} for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])] = 0
for h in range(H):
    for w in range(W):
        for v in dp[h][w]:
            if w != W-1:
                dp[h][w+1][abs(v+A[h][w+1]-B[h][w+1])] = 0
                dp[h][w+1][abs(v-A[h][w+1]+B[h][w+1])] = 0
            if h != H-1:
                dp[h+1][w][abs(v+A[h+1][w]-B[h+1][w])] = 0
                dp[h+1][w][abs(v-A[h+1][w]+B[h+1][w])] = 0
ans = min(dp[H-1][W-1])
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split(" "))

count = 0
for x in range(0, k+1):
	for y in range(0, k+1):
		for z in range(0, k+1):
			if x+y+z == s:
				count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split(" "))

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            count += 1

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

def main():
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n+1)]
    for i,j in zip(*[iter(py)]*2):
        d[i].append(j)

    for i in d:
        i.sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = d[i].index(j) + 1
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import bisect
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(py)] * 2):
        d[i].append(j)

    for i in d:
        i.sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = bisect.bisect_right(d[i], j)
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


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

from collections import deque
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]
A=[[0]*W for _ in range(H)]
ans=[]

for i in range(H):
    for j in range(W):
        c=0
        sy=i
        sx=j
        A[i][j]=1
        route=deque([(sy,sx,0)])
        while route:
            a,b,n=route.popleft()
            c=n
            if 0<=a<=H-1 and 0<=b<=W-1:
                if S[a][b]=='.':
                    S[a][b]=='#'
                    route.append((a+1,b,n+1))
                    route.append((a-1,b,n+1))
                    route.append((a,b+1,n+1))
                    route.append((a,b-1,n+1))
        ans.append(c)

print(max(ans))
                        

### FIXED CODE ###

from collections import deque
import copy
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]
S1=copy.deepcopy(S)
ans=[]

sy=0
sx=0
for i in range(H):
    for j in range(W):
        c=0
        route=deque([(i,j,0)])
        S=copy.deepcopy(S1)
        while route:
            a,b,n=route.popleft()
            c=n
            if 0<=a<=H-1 and 0<=b<=W-1:
                if S[a][b]=='.':
                    S[a][b]='#'
                    route.append((a+1,b,n+1))
                    route.append((a-1,b,n+1))
                    route.append((a,b+1,n+1))
                    route.append((a,b-1,n+1))
                    
        ans.append(c-1)

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

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

    
N, K = mi()
A = li()

#light = [0] * (N+2)
#A = [0] + A + [0]

for i in range(K):
    new = [0] * (N+1)
    for j in range(N):
        new[max(j-A[j], 0)] += 1
        new[min(j+A[j]+1, N)] += -1
        #print(new)
    new = list(accumulate(new))
    A = new[:N]
    if sum(A) == N **2:
        for i in range(N):
            print(N, '', end='')
        print()
        exit()
    #print(tmp)

for i in range(N):
    print(A[i], '', end='')
print()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math
    
N, K = mi()
A = li()
 
#light = [0] * (N+2)
#A = [0] + A + [0]
#print(math.log(N, 2))
'''
thre = 0
for i in range(N):
    if A[i] < i:
        thre = max(thre, i-A[i])
'''
if K > pow(N, 0.5) + 1:
        for i in range(N):
            print(N, '', end='')
        print()
        exit()
 
 
for i in range(K):
    new = [0] * (N+1)
    for j in range(N):
        new[max(j-A[j], 0)] += 1
        new[min(j+A[j]+1, N)] += -1
        #print(new)
    new = list(accumulate(new))
    A = new[:N]
 
for i in range(N):
    print(A[i], '', end='')
print()
### BUGGY CODE ###

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

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

b = []
for i in range(k-1,n):
    c = 1
    for j in range(k):
        c *= a[i - j]
    b.append(c)

for i in range(n-k):
    if b[i] < b[i + 1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

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

for i in range(k,n):
    if a[i-k] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from itertools import accumulate

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

M = N*(N+1)//2

def isOK(mid):
    Ss = [1 if A >= mid else -1 for A in As]
    Ss = list(accumulate([0]+Ss))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    iSs = list(range(N+1))
    iSs.sort(key=lambda iS: Ss[iS])
    odrSs = [0]*(N+1)
    for odrS, iS in enumerate(iSs):
        odrSs[iS] = odrS

    num = 0
    for odrS in odrSs:
        num += getSum(odrS)
        addValue(odrS, 1)
    return num >= (M+1)//2


ng, ok = 10**9+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

from itertools import accumulate

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

Bs = sorted(As)
M = N*(N+1)//2

def isOK(mid):
    Am = Bs[mid]
    Ss = [1 if A >= Am else -1 for A in As]
    Ss = list(accumulate([0]+Ss))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    iSs = list(range(N+1))
    iSs.sort(key=lambda iS: Ss[iS])
    odrSs = [0]*(N+1)
    for odrS, iS in enumerate(iSs):
        odrSs[iS] = odrS

    num = 0
    for odrS in odrSs:
        num += getSum(odrS)
        addValue(odrS, 1)
    return num >= (M+1)//2


ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(Bs[ok])
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys
import random

import numpy as np


def is_prime3(q, k=50):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


like2017 = [1 if is_prime3(i) and is_prime3((i + 1) // 2) else 0 for i in range(100000 + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l-1])


### FIXED CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])