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

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

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

    #[行先, 距離]
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        l,r,d = map(int, input().split())
        adj[l-1].append([r-1, d])
        adj[r-1].append([l-1, -d])

    x = [inf]*n

    def dfs(v):
        if x[v]==inf:
            x[v] = 0
        d = deque([v])
        while d:
            v  = d.popleft()
            for nv, cost in adj[v]:
                if x[nv] == inf:
                    x[nv] = x[v] + cost
                else:
                    if x[nv] - x[v] != cost:
                        return False
                d.append(nv)
        return True


    for v in range(n):
        if not dfs(v):
            print('No')
            exit()
    print('Yes')


if __name__ == '__main__':
    main()




### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

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

    #[行先, 距離]
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        l,r,d = map(int, input().split())
        adj[l-1].append([r-1, d])
        adj[r-1].append([l-1, -d])

    x = [inf]*n

    def dfs(v):
        if x[v]==inf:
            x[v] = 0
        d = deque([v])
        while d:
            v  = d.popleft()
            for nv, cost in adj[v]:
                if x[nv] == inf:
                    x[nv] = x[v] + cost
                    d.append(nv)
                else:
                    if x[nv] - x[v] != cost:
                        return False
        return True


    for v in range(n):
        if not dfs(v):
            print('No')
            exit()
    print('Yes')


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

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

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dic_Lg = {}
    dic_Lw = {}
    for i in range(N):
        x = i - A[i]
        if x in dic_Lg:
            dic_Lg[x]+=1
        else:
            dic_Lg[x]=1
        y = i + A[i]
        if y in dic_Lw:
            dic_Lw[y]+=1
        else:
            dic_Lw[y]=1
        LP = list(dic_Lw.keys()) + list(dic_Lg.keys())
        LP = set(LP)

    ret = 0
    for i in LP:
        if i in dic_Lg and i in dic_Lw:
            ret += dic_Lg[i] * dic_Lw[i]
    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

import sys

from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dic_Lg = {}
    for i in range(N):
        x = i - A[i]
        if x in dic_Lg:
            dic_Lg[x].append(i)
        else:
            dic_Lg[x]=[i]
    ret = 0
    for i in range(N):
        y = i+A[i]
        if not y in dic_Lg:
            continue
        arr = dic_Lg[y]
        r = bisect_right(arr, i)    # 5が入るべき境目のうち最も右側の境目を返す
        ret += len(arr)-r
    print(ret)

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

n,q =map(int,input().split())
s=input()
p=[[int(j) for j in input().split()] for i in range(q)]
for k in range(q):
    print(s[p[k][0]-1:p[k][1]].count("AC"))




### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

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

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        for l in range(k + 1):
            if i + j + l == s:
                count += 1

print(count)


### FIXED CODE ###

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

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

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

import sys
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    aList = list(map(int, readline().rstrip().split()))
    aMax = max(aList)
    for i in range(n):
        if aMax >= i + 1:
            print(aList.count(i + 1))
        else:
            print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    aList = sorted(list(map(int, readline().rstrip().split())))
    z = [0] * n
    for a in aList:
        z[a-1] += 1

    for i in range(n):
        print(z[i])


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

A, B, K = (int(x) for x in input().split())

for i in range(K):
    if A > 0:
        A -= 1
    elif B > 0:
        B -= 1
    else:
        pass

print(A, B)


### FIXED CODE ###

A, B, K = (int(x) for x in input().split())

M = A + B
if K >= M:
    A = 0
    B = 0
else:
    if K >= A:
        B = B - (K - A)
        A = 0
    else:
        A = A - K

print(A, B)
### BUGGY CODE ###

S = int(input())
A = input()
z = ''
arr1 = [i for i in A.split(' ')]
for i in range(S):
	for j in range(i+1, S):
		if(arr1[i]==arr1[j]):
			z = 'NO'
			break
if(z=='NO'):
	print(z)
else:
	print('YES')

### FIXED CODE ###

n = int(input())
arr = [int(n) for n in input().split()]
_set = set()
for i in range(0, n):
    _set.add(arr[i])
print("YES") if len(_set) == len(arr) else print("NO")
### BUGGY CODE ###

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

for i in range(m,0,-1):
    if (m%i==0 and n<=m//i):
       print(i)
       exit(0) 


### FIXED CODE ###

import math
n,m = map(int, input().split())
factors = []
comp = m//n
for i in range(int(math.sqrt(m)),0,-1):
    if(m%i==0):
        factors.insert(0,i)
        factors.append(m//i)
for item in factors[::-1]:
    if (item <= comp):
        print(item)
        exit(0)
### BUGGY CODE ###

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

    c = 0

    r_indices = [i for i in range(N) if S[i] == 'R']
    g_indices = [i for i in range(N) if S[i] == 'G']
    b_indices = [i for i in range(N) if S[i] == 'B']

    # print(r_indices)
    # print(g_indices)
    # print(b_indices)

    for r in r_indices:
        for g in g_indices:
            for b in b_indices:
                # print(r + g + b)
                # print(r + g + b)
                if r + g + b != 3 * (max([r, g, b]) + min([r, g, b])) / 2:
                    c += 1

    print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    c = 0

    r_indices = tuple([i for i in range(N) if S[i] == 'R'])
    g_indices = tuple([i for i in range(N) if S[i] == 'G'])
    b_indices = tuple([i for i in range(N) if S[i] == 'B'])

    # print(r_indices)
    # print(g_indices)
    # print(b_indices)

    avoid = 0

    for center in range(1, N - 1):
        # print('###')
        # print('center = ', center)
        # print(min(center, N - center - 1))

        for width in range(1, min(center + 1, N - center)):
            # print('c, w = ', center, width)
            little = center - width
            great = center + width
            # print('little=', little)
            # print('center=', center)
            # print('great=', great)

            if S[little] != S[great] and S[center] != S[great] and S[little] != S[center]:
                avoid += 1

    total = len(r_indices) * len(g_indices) * len(b_indices)

    print(total - avoid)


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

k = int(input())


def gcd_arg2(a, b):
    if b == 0:
        return a
    return gcd_arg2(b, a % b)

def gcd_arg3(a,b,c):
    return gcd_arg2(c,gcd_arg2(a,b))

ans_list = list()
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans_list.append(gcd_arg3(a,b,c))

print(sum(ans_list))

### FIXED CODE ###

import math
def gcd_arg3(a,b,c):
    return math.gcd(a,math.gcd(b,c))

k = int(input())

sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        gcd_a_b = math.gcd(a,b)
        for c in range(1,k+1):
            sum += math.gcd(gcd_a_b,c)

print(sum)
### BUGGY CODE ###

H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

def steppable(h,w):
    if not (h in range(H)) or not (w in range(W)):
        return False
    if S[h][w] == '#':
        return False
    else:
        return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        num_step[h[0]][h[1]] = num_warp
        # ゴールチェック
        if num_step[Dh - 1][Dw - 1] != INF:
            print(num_step[Dh - 1][Dw - 1])
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] > num_warp:
                    # print(S[h[0] + y][h[1] + x])
                    # print((h[0] + y, h[1] + x))
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            queue.append((magic[0],magic[1]))

print(-1)

### FIXED CODE ###

H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)
### BUGGY CODE ###

from fractions import gcd
 
def primeNum(n):
  prime=[1]
  for k in range(2, n+1):
    if n % k == 0:
      prime.append(k)
      while n % k == 0:
        n = n // k
  return prime
 
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(len(primeNum(n)))

### FIXED CODE ###

from fractions import gcd
 
def primeNum(n):
  ans = 1
  if n == 1:
    return ans
  if n % 2 == 0:
    ans += 1
    while n % 2 == 0:
      n = n // 2
  for k in range(3, int(n**0.5)+1, 2):
    if n % k == 0:
      ans += 1
      while n % k == 0:
        n = n // k
    if n == 1:
      return ans
  if n != 1:
    ans += 1
  return ans
  
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(primeNum(n))
### BUGGY CODE ###

import math

n, m = [int(i) for i in input().split()]


def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += combi(k - i, i)
    ans = ans * cnt % 1000000007

print(ans)


### FIXED CODE ###

n, m = [int(i) for i in input().split()]

b = [0 for i in range(n+1)]

for mi in range(m):
    b[int(input())] = 1
cnt = 0
s = [0 for i in range(n+1)]
s[0] = 1
if b[1] == 0:
    s[1] = 1
else:
    s[1] = 0
for ni in range(2,n+1):
    if b[ni] == 0:
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else:
        s[ni] = 0
print(s[n])
### BUGGY CODE ###

N=int(input())
a = list(map(int, input().split()))
import fractions
ansp = a[0]
ans = 1
for i in a[1:]:
  ansn = ansp * i // fractions.gcd(ansp, i)
  ans = ans * (ansn // ansp) + ansn // i
  ans = ans % (10**9+7)
  ansp = ansn
print(ans)



### FIXED CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ans = 0
for i in a:
    ans += (lcm//i)#%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

N,M = map(int,input().split())
AB= []
for i in range(N):
    AB.append([int(j) for j in input().split()])

AB = sorted(AB, key=lambda x: x[0])
AB = sorted(AB, key=lambda x: x[1], reverse=True)
#お金が高い＞日にちがかからない　の順にソート

for i in range(N):  #同じ仕事があっても消せるようにIDを振る
    AB[i].append(i)

money = 0

def NdayOK(n):  #あとn日残されているときに選べる仕事のリスト
    nd = []
    for i in range(N):
        if AB[i][0] <= n:
            nd.append(AB[i][2])
    return(nd)

checker = []
for i in range(M+1):
    NOi = NdayOK(i)
    for j in NOi:
        if AB[j][2] not in checker:
            money += AB[j][1]
            checker.append(AB[j][2])
            break

print(money)

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
L=[[] for i in range(M+1)]

for i in range(N):
    if AB[i][0]<=M:
        L[AB[i][0]].append(-AB[i][1])

LL=[]
money=0

for i in range(1,M+1):
    for j in L[i]:
        heapq.heappush(LL,j)
    if len(LL)==0:
        continue
    money+=heapq.heappop(LL)

print(-money)
### BUGGY CODE ###

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

white = 0
black = 0
index = 0

ans = []

for i in range(N):
  white = S[0:i].count("#")
  black = S[i+1:N+1].count(".")
  ans.append(white+black)

print(min(ans))


### FIXED CODE ###

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

white = S.count(".")
black = 0
ans = S.count(".")

for i in range(N):
  if S[i] == ".":
    white -=1
  else:
    black +=1
  ans = min(ans,white+black)

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

import math
import collections
n=int(input())
a=list(map(int,input().split()))
for i in a:
    c=collections.Counter(a)
    ans=0
    c[i] -=1
    for k in c.values():
        if k != 1:
            ans +=k*(k-1)//2
    print(ans)

### FIXED CODE ###

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

# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[float('inf') for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == float('inf'):
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


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

from collections import Counter
N = int(input())
A = map(int, input().split())
Q = int(input())
ops = []
for _ in range(Q):
  b, c = map(int, input().split())
  ops.append((b,c))

tot = []
cnt = Counter(A)
for b, c in ops:
  #print(cnt)
  #print(b, c)
  cnt[c] += cnt[b]
  cnt[b] = 0
  s = sum(k*v for k, v in cnt.items())
  print(s)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = map(int, input().split())
Q = int(input())
ops = []
for _ in range(Q):
  b, c = map(int, input().split())
  ops.append((b,c))

cnt = Counter(A)
s = sum(k*v for k, v in cnt.items())
for b, c in ops:
  s -= b * cnt[b]
  s += c * cnt[b]
  cnt[c] += cnt[b]
  cnt[b] = 0
  print(s)
### BUGGY CODE ###

from collections import Counter

N = int(input())

F    = [None] * (N+1)
F[0] = 1

for i in range(1, N+1):
    F[i] = F[i-1] * i

S = [''.join(sorted(list(input()))) for i in range(N)]

print(sum([F[i] // F[i-2] // 2 for i in Counter(S).values()]))


### FIXED CODE ###

import math

from collections import Counter


def func(i):
    if i >= 1:
        return math.factorial(i)
    else:
        return 1


N = int(input())

S = [''.join(sorted(list(input()))) for i in range(N)]

print(sum([func(i) // func(i-2) // 2 for i in Counter(S).values()]))
### BUGGY CODE ###

# 小さいのでメモ化再帰でいけるか？
# （[ここまでの回答数, ここまでの点数]みたいなやつ）
# んーーーーーー？？？？ RE*1、あとTLEになる。。。
# REはどうせ再帰の制限
import sys

sys.setrecursionlimit(10 ** 8)

d, g = map(int, input().split())
memo = {}
points, bonus = [], []
for _ in range(d):
    p, c = map(int, input().split())
    points.append(p)
    bonus.append(c)


def f(c, p):
    if (c, p) in memo:
        return memo[(c, p)]
    if p >= g:
        return c
    ret = 10 ** 10
    for i in range(d):
        if points[i] == 1:
            points[i] = 0
            ret = min(ret, f(c + 1, p + (i + 1) * 100 + bonus[i]))
            points[i] = 1
        elif points[i] > 1:
            points[i] -= 1
            ret = min(ret, f(c + 1, p + (i + 1) * 100))
            points[i] += 1
        else:
            continue
    memo[(c, p)] = ret
    return ret


print(f(0, 0))


### FIXED CODE ###

# 未知のアルゴリズムか天才系DPかと思ってすぐ諦めて解説読んでしまった

d, g = map(int, input().split())
points = []
for _ in range(d):
    p, c = map(int, input().split())
    points.append((p, c))
ans = 10**12
for bit in range(2**d):
    arr = [False] * d
    for i in range(d):
        if bit >> i & 1 == 1:
            arr[i] = True
    tmp_sum = 0
    count = 0
    for i in range(d):
        if arr[i]:
            # kompuli-to
            tmp_sum += points[i][1]
            tmp_sum += (i + 1) * 100 * points[i][0]
            count += points[i][0]
    if tmp_sum < g:
        # 達成できるまで得点の高いやつからやっていく
        for i in range(d - 1, -1, -1):
            if arr[i]:
                # すでにkompuli-toしてるので
                continue
            used = 0
            for j in range(points[i][0]):
                if tmp_sum < g:
                    tmp_sum += (i + 1) * 100
                    count += 1
                    used += 1
            if used == points[i][0]:
                tmp_sum += points[i][1]
            if tmp_sum >= g:
                break
    ans = min(ans, count)
print(ans)
### BUGGY CODE ###

import sys,math

_primes = {1:False,2:True}
like2017 = {}

def isPrime(num):
    if num not in _primes:
        for i in range(2,max(2,math.floor(math.sqrt(num))+1)):
            if num%i == 0:
                _primes[num] = False
                break
        else:
            _primes[num] = True
    return _primes[num]

def isLike(num):
    if num not in like2017:
        like2017[num] = True if (isPrime(num) and isPrime((num+1)/2)) else False
    return like2017[num]

Q = int(input())
for i in range(Q):
    S,G = list(map(int,input().split()))
    print(sum(isLike(x) for x in range(S,G+1,2)))

### FIXED CODE ###

prime = {1:False}
for i in range(2,100001):
    if i not in prime:
        prime[i] = True
        for j in range(i*2,100001,i):
            prime[j] = False

like = {0:0}
for i in range(1,100001):
    like[i] = like[i-1] + int((i%2==1) and prime[i] and prime[int((i+1)/2)])

Q = int(input())
for i in range(Q):
    LR = list(map(int,input().split()))
    print("%d"%(like[LR[1]]-like[LR[0]-1]))