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

import math
n, a, b = map(int, input().split())
d = []
for i in range(n):
    d.append(input())
# [d1, d2, d3, ..., dN]
h = [int(m) for m in d]#int型に直す
#print(x)

low = 0
high = math.ceil(max(h)/b)
# t は中央番目の数
t = (low + high) // 2

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかっTrueたということ
X = 0
Y = 0
while True:
    for j in range(n):
        X += max(0, math.ceil((h[j] - t * b) / (a - b)))
    if X <= t:
        for j in range(n):
            Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))
        if Y > t - 1:
            print(t)
            exit()
        else:
            high = t - 1
    elif X > t:
        low = t + 1
    t = (low + high) // 2
    X = 0
    Y = 0

### FIXED CODE ###

import math
n, a, b = map(int, input().split())
d = []
for i in range(n):
    d.append(input())
# [d1, d2, d3, ..., dN]
h = [int(m) for m in d]#int型に直す
#print(x)

low = 0
high = math.ceil(max(h)/b)
# t は中央番目の数
t = (low + high) // 2

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかっTrueたということ
X = 0
Y = 0
s = 0
while high - low >= 0:
    for j in range(n):
        X += max(0, math.ceil((h[j] - t * b) / (a - b)))
        #Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))
    if X == t:
        print(t)
        exit()
    elif X < t:
        high = t - 1
        """for j in range(n):
            Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))"""
    elif X > t:
        low = t + 1
    s = t
    t = (low + high) // 2
    X = 0
    Y = 0
for j in range(n):
  if math.ceil((h[j] - s * b) / (a - b)) > 0:
            Y += math.ceil((h[j] - s * b) / (a - b))
if Y <= s:
  print(s)
else:
  print(s + 1)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
A,B,C= [[int(i) for i in input().split()] for j in range(3)]
AB = []
ABC = []
for i in range(x):
        for j in range(y):
                AB.append(A[i]+B[j])
AB_sort = sorted(AB,reverse=True)
for i in range(min(k,len(AB))):
        for j in range(z):
                ABC.append(AB_sort[i]+C[j])
ABC_sort = sorted(ABC,reverse = True)
for i in range(k):
        print(ABC_sort[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x * i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))


### FIXED CODE ###

x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x and i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))
### BUGGY CODE ###

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

### FIXED CODE ###

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

import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
d = [[float('inf') for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    t = min(c, d[a][b])
    if d[a][b] > c:
        d[a][b], d[b][a] = t, t

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = float('inf')
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j - 1]
        else:
            flag = True
        prev = j - 1
    ans = min(ans, temp)

print(ans)


### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
### BUGGY CODE ###

import collections
import itertools


def p_c():
    n = int(input())
    l = []
    ans = 0

    for _ in range(n):
        l.append(collections.Counter(input()))

    for i in list(itertools.combinations(l, 2)):
        if i[0] == i[1]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    p_c()

### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

for i in range(n):
    i_ = (n+i)%n
    s_ = s[i_:] + s[:i_]
    for k in range(n):
        for l in range(k+1, n):
            if s_[k][l] != s_[l][k]:
                break
        else:
            continue
        break
    else:
        cnt += 1

print(cnt*n)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

def is_symmetry(s_):
    for k in range(n):
        for l in range(k+1, n):
            if s_[k][l] != s_[l][k]:
                return False
    return True

for i in range(n):
    i_ = (n+i)%n
    s_ = s[i_:] + s[:i_]
    if is_symmetry(s_):
        cnt += 1

print(cnt*n)
### BUGGY CODE ###


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

L.sort()
#print(L)

count = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        L_ = L[j+1:]
        #print(L[i] + L[j], ">", L_, "?")
        key = len(L_) // 2
        #print("init key", key)
        past_key = 0
        while key:
            if L[i] + L[j] > L_[key]:
                key = key + round((len(L_) - key) / 2)
            elif L[i] + L[j] <= L_[key]:
                key = round(key / 2)
            
            if past_key == key:
                break
            else:
                past_key = key
            #print("next key", key)
            
        if L[i] + L[j] > L_[key]:
            count += key + 1
            

print(count)

### FIXED CODE ###

def fnt(arr,n): 
  
     
     
     
    count = 0
  
     
    for i in range(0,n-2): 
  
         
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
             
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
             
            if(k>j): 
                count += k - j - 1
  
    return count
 
 
n=int(input())
arr=input()
arr=arr.split()
arr=list(map(int,arr))
arr.sort()
print(fnt(arr,n))
### BUGGY CODE ###

n = int(input())
a = list(input().split())
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(' '.join(b))

### FIXED CODE ###

n = int(input())
a = list(input().split())
b = []
a = a[::-1]
for i in range(n)[::2]:
    b.append(a[i])
a = a[::-1]
if n % 2 != 0:
    a.pop(0)
for i in range(len(a))[::2]:
    b.append(a[i])
print(' '.join(b))
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(map(int, input().split()))

c=[0]*max(a)
for i in range(n): 
    m=a[i]
    pf={}
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1

    for k in pf:
        c[k-1]+=1
        
maxcount=max(c)

if np.gcd.reduce(a) != 1:
    print('not coprime')
elif maxcount <= 1:
    print('pairwise coprime')
else:
    print('setwise coprime')
    

### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int, input().split()))

if np.gcd.reduce(a) != 1:
    print('not coprime')
    exit()

m=max(a)
cnt=[0]*(m+1)

for i in range(len(a)):
    cnt[a[i]]+=1
#print(cnt)
for i in range(2, m + 1):
    #print(cnt[i::i])
    if sum(cnt[i::i]) > 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')
### BUGGY CODE ###

import itertools

N = int(input())

ans = {}
for v in itertools.combinations_with_replacement(range(1,(N//6)+1), 3):
    x,y,z = v
    count = 0
    if x == y == z:
        fn = 6 * x * x
        count = 1
    else:
        fn = x*x + y*y + z*z + x*y + y*z + z*x
        count = 3
    if fn in ans.keys():
        ans[fn] += count
    else:
        ans[fn] = count

for i in range(1,N+1):
    if i in ans.keys():
        print(ans[i])
    else:
        print(0)


### FIXED CODE ###

N = int(input())
ans = [0 for _ in range(1,10101)]

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n < N+1:
                ans[n-1] += 1

print(*ans[:N],sep='\n')
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


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


# In[2]:


link = [[] for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    link[L-1].append((R-1, D))
    link[R-1].append((L-1, -D))


# In[3]:


def func():
    houmon = [False] * N

    for start in range(N):
        x = [0] * N
        if houmon[start]:
            continue
        stack = [start]
        while stack:
            n1 = stack.pop()
            houmon[n1] = True
            for n2, d in link[n1]:
                if houmon[n2]:
                    if x[n2] != x[n1] + d:
                        return False
                else:
                    x[n2] = x[n1] + d
                    stack.append(n2)
        
#         if max(x) - min(x) > 10 ** 9:
#             return False
    
    return True


# In[4]:


if func():
    print('Yes')
else:
    print('No')



### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[13]:


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


# In[14]:


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


# In[2]:


link = [[] for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    link[L-1].append((R-1, D))
    link[R-1].append((L-1, -D))


# In[9]:


def func():
    houmon = [False] * N
    x = [0] * N
    
    for start in range(N):
        if houmon[start]:
            continue
        stack = deque([start])
        while stack:
            n1 = stack.pop()
            houmon[n1] = True
            for n2, d in link[n1]:
                if houmon[n2]:
                    if x[n2] != x[n1] + d:
                        return False
                else:
                    x[n2] = x[n1] + d
                    stack.append(n2)
        
#         if max(x) - min(x) > 10 ** 9:
#             return False
    
    return True


# In[10]:


if func():
    print('Yes')
else:
    print('No')


# In[ ]:
### BUGGY CODE ###

import collections
import math

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

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

    Cou = collections.Counter(A)

    C_d = {}

    '''
    for k, c in Cou.items():
        if c > 1:
            C_d[k] = comb(c, 2)
        else:
            C_d[k] = 0
    print(C_d)
    '''
    ans = 0
    for k in range(1, N+1):
        tmp = Cou.copy()
        tmp[A[k-1]] -= 1
        ans = 0
        #print(tmp)
        for c in tmp.values():
            if c > 1:
                ans += comb(c, 2)

        print(ans)
        #tmp[A[k-1]] = max(0, tmp[A[k-1]]-2)
        #print(sum(tmp.values()))


    return 0


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections
import math

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

    Cou = collections.Counter(A)
    ans = 0

    oo = 0
    for c in Cou.values():
        oo += c * (c-1) // 2
    #print(Cou)
    for k in range(1, N+1):
        c = Cou[A[k-1]] - 1
        print(oo - c)
    return 0


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

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

sum=0
for i in range(n):
    sum=sum+a[i]

for j in range(1,n,2):
    sum=sum-a[j]*2

ans=[sum]
ch=sum
for i in range(0,n-1):
    ch=a[i]*2-ch
    ans.append(ch)


aaa=str(ans[0])
for i in range(1,n):
    ccd=str(ans[i])
    aaa=aaa+' '+ccd
print(aaa)

### FIXED CODE ###

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

sum=0
for i in range(n):
    sum=sum+a[i]

for j in range(1,n,2):
    sum=sum-a[j]*2

ans=[sum]
ch=sum
for i in range(0,n-1):
    ch=a[i]*2-ch
    ans.append(ch)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = [int(a) for a in input().split()]

for k in range(N):
    a = [0] * N
    sum = 0
    for i in range(N):
        a[A[i]-1] += 1
    a[A[k]-1] -= 1
    for i in range(N):
        if a[i] >= 2:
            sum += combinations_count(a[i], 2)
    print(sum)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
a = [0] * N
for i in A:
    a[i-1] += 1
cnt = 0
cnt += sum([i*(i-1)//2 for i in a])
for i in A:
    print(cnt - (a[i-1]-1))
### BUGGY CODE ###

n,m = map(int,input().split())
num_list = list(map(int,input().split()))
num_list.sort()
d_list = []
if n >= m:
    print(0)
    
else:
    for i in range(m-1):
        tmp = num_list[i+1] - num_list[i]
        d_list.append(tmp)
        d_list.sort(reverse = True)
    print(sum(d_list[n-1:]))

### FIXED CODE ###

n,m = map(int,input().split())
num_list = list(map(int,input().split()))
num_list.sort()
d_list = []
if n >= m:
    print(0)
    
else:
    for i in range(m-1):
        tmp = num_list[i+1] - num_list[i]
        d_list.append(tmp)
    d_list.sort(reverse = True)
    print(sum(d_list[n-1:]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
wt,p=[],[]
cache={}
def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache.get((W,n)):
    return cache[(W,n)]
  
  else:
    if wt[n-1]<=W:
      cache[(W,n)]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[(W,n)]=knapsack(W,n-1)
    
    return cache[(W,n)]

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

for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))



### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
### BUGGY CODE ###

def check(s, a, next):
    if a==next:
        return False
    x = 1
    while a>=x*x:
        if a%x==0:
            if x in s:
                return False
            if a//x in s:
                return False
        x += 1
    return True

n = int(input())
al = list(map(int, input().split()))
al.sort()

s = set()
res = 0
for i in range(n):
    a = al[i]
    next = -1
    if i<n-1:
        next = al[i+1]
    if check(s,a,next):
        res += 1
    s.add(a)
print(res)



### FIXED CODE ###

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

cnt = [0]*(10**6+10)
for a in al:
    if cnt[a]>1:
        continue
    for i in range(0,10**6+10,a):
        cnt[i] += 1

res = 0
for a in al:
    if cnt[a]==1:
        res += 1
print(res)
### BUGGY CODE ###

n = int(input())

res=0

for i in range(1,n):
    for j in range(1,n):
        if i*j < n:
            res+=1
        else:
            break

print(res)

### FIXED CODE ###

from math import ceil
n = int(input())

res=0

for i in range(1,ceil(n/2)):
    for j in range(i+1,n):
        if i*j < n:
            res+=1
        else:
            break

if int(n**0.5) == n**0.5:
    print(res*2 + int(n**0.5) - 1)
else:
    print(res*2 + int(n**0.5))
### BUGGY CODE ###

from collections import deque
import sys
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

maze = []
for i in range(H):
    maze.append(list(input()))

cnt = 0

def bfs():
    global cnt
    reached = [[False for _ in range(W)] for _ in range(H)]

    d = deque()
    d.append((Ch, Cw))
    #reached[Ch][Cw] = True
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            d.append((i, j))
        if d:
            cnt += 1

bfs()
print(-1)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a_int = list(map(int, input().split()))
squ = 0
for i in range(0, n-1):
    for j in range(i+1, n):
        squ += a_int[i] * a_int[j]
ans = squ % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

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

squ = 0
num = 10 ** 9 + 7

a_sum = 0
for i_sum in range(1, n):
    a_sum += a_int[i_sum]

for i in range(0, n-1):
    squ += a_int[i] * a_sum
    a_sum -= a_int[i+1]

ans = squ % num
print(ans)
### BUGGY CODE ###

def is_prime(x):
  if x == 1:
    return False
  for i in range(2, x):
    if x % i == 0:
      return False
    if i * i>= x:
      break         #breakにしないと膨大な数字をいつまでも追いかけている
  return True

def check(l,r):
  count = 0
  for i in range(l,r+1,2):
    if is_prime(i) == True:
      if is_prime((i+1)//2) == True:
        count += 1
  return count


Q = int(input())

nums = []
for i in range(Q):
  l,r = map(int,input().split())
  nums.append(check(l,r))


for i in nums:
  print(i)



### FIXED CODE ###

NMAX = 10**5+1

is_prime = [True]*NMAX
for i in range(2, NMAX):
    if is_prime[i]:
        for j in range(2*i, NMAX, i):
            is_prime[j] = False

sim_2017 = [0]*NMAX
for i in range(3, NMAX, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        sim_2017[i] += 1
for i in range(1, NMAX):
    sim_2017[i] += sim_2017[i-1]

q = int(input())
for _ in range(q):
    l, r = list(map(int, input().split()))
    ans = sim_2017[r] - sim_2017[l-1]
    print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))

todo = deque()
done = set()
ans = 0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == "#":
            continue
        s = (sh, sw)
        done.clear()
        todo.append((s, 0))
        while todo:
            p, count = todo.popleft()
            ans = max(ans, count)
            done.add(p)
            ncount = count + 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh = p[0] + dh
                nw = p[1] + dw
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                todo.append((np, ncount))
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))

todo = deque()
done = set()
ans = 0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == "#":
            continue
        s = (sh, sw)
        done.clear()
        done.add(s)
        todo.append((s, 0))
        while todo:
            p, count = todo.popleft()
            ncount = count + 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh, nw = p[0] + dh, p[1] + dw
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                done.add(np)
                ans = max(ans, ncount)
                todo.append((np, ncount))
print(ans)