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

import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def dijkstra(s, n, edge):
    res = [float("inf")] * n
    res[s] = 0
    hq = []
    heapq.heappush(hq, [0, s])
    while hq:
        ci, i = heapq.heappop(hq)
        if res[i] < ci:
            continue
        for cj, j in edge[i]:
            if res[j] > (res[i] + cj):
                res[j] = res[i] + cj
                heapq.heappush(hq, [res[j], j])
    return res


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    edge = [[] for j in range(H * W)]
    for i in range(H):
        for j in range(W):
            for k in range(-2, 3):
                for l in range(-2, 3):
                    ni = i + k
                    nj = j + l
                    if k == 0 and l == 0:
                        continue
                    if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                        if abs(k) + abs(l) >= 2:
                            edge[i * W + j].append([1, ni * W + nj])
                        else:
                            edge[i * W + j].append([0, ni * W + nj])
    ans = dijkstra(CH * W + CW, H * W, edge)
    if ans[DH * W + DW] == float("inf"):
        print(-1)
    else:
        print(ans[DH * W + DW])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2],
            [-1, -2], [-1, -1], [-1, 1], [-1, 2],
            [0, 2], [0, -2],
            [1, -2], [1, -1], [1, 1], [1, 2],
            [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.appendleft((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


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

from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]
dict={".":10000000,"#":-1}
sy,sx,gy,gx=c[0]-1,c[1]-1,d[0]-1,d[1]-1
s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
s[sy][sx]=0
que=deque([[sy,sx]])
temp=[(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]
while que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]>=0:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and dist>s[y][x]:
                s[nexty][nextx]=s[y][x]
                que.append([nexty,nextx])
            elif dist>s[y][x]+1:
                s[nexty][nextx]=s[y][x]+1
                que.append([nexty,nextx])

if s[gy][gx]==10000000:
    print(-1)
else:
    print(s[gy][gx])


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        ans+=1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
  for y in range(0,k+1):
    tmp = s - (x+y)
    if tmp>=0 and tmp<k+1:
      ans+=1
print(ans)
### BUGGY CODE ###

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

a1,b1,a2,b2=map(int,input().split())
score=comb(a2+b2+2,a2+1)-comb(a2+b1+1,a2+1)-comb(a1+b2+1,a1)+comb(a1+b1,a1)
print(score%(10**9+7))

### FIXED CODE ###

a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
R = max(a2+1,b2+1)
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	if s[-1] == "1":
		print(1)
		continue
	else:
		i = 0
		while i < n and s[i] == "0":
			i += 1
		if i == n:
			print(0)
			continue
		ok = True
		o, z = {0}, {0}
		while i < n:
			while s[i] == "1":
				o_new = set()
				for x in o:
					o_new.add(x)
					o_new.add(x^a[i])
				o = o_new
				i += 1
			while i < n and s[i] == "0":
				z_new = set()
				for x in z:
					z_new.add(x)
					z_new.add(x^a[i])
				z = z_new
				i += 1
			if not o.issubset(z):
				ok = False
				break
		if ok:
			print(0)
		else:
			print(1)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

def least_bit_set(x):
	return x & (-x)


def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]


def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		values[i], values[j] = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1


def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0



#values = [1, 5, 8, 2, 10]
#eliminated_values = eliminate(values)
#print(eliminated_values)
#x = int(input())
#print(in_span(x, eliminated_values))

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	values = []
	ok = True
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			values.append(a[i])
		else:
			elim = eliminate(values)
			if not in_span(a[i], elim):
				ok = False
				break
	if ok:
		print(0)
	else:
		print(1)
### BUGGY CODE ###

n = int(input())
numbers = list(map(int, input().split(' ')))

counters = {}
for i in numbers:
    counters[i] = numbers.count(i)
for i in range(n):
    sonuc = 0
    for sayi in counters:
        count = counters[sayi]
        if numbers[i] == sayi:
            count -= 1
        sonuc += count*(count-1)/2
    print(int(sonuc))


### FIXED CODE ###

n = int(input())
numbers = list(map(int, input().split(' ')))

counters = {}
cevap_list = {}
sayilar = set(numbers)
for i in numbers:
    if i in counters:
        counters[i] += 1
    else:
        counters[i] = 1

sonuc = 0
for sayi in counters:
    count = counters[sayi]
    sonuc += int(count * (count - 1) / 2)


for i in range(n):
    print(sonuc-counters[numbers[i]]+1)
### BUGGY CODE ###

import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    que = list(sorted(que, key=lambda _: _[2]))
    ans = 0
    while que != []:
        u, v, d = que.pop(0)
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            parent[u] = v
    return ans

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

### FIXED CODE ###

import numpy as np

def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = [i for i in range(n)]
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))
### BUGGY CODE ###

n = int(input())
data_input = []
dlList = []
for i in range(n):
    x = input().split()
    if x[0] == 'insert':
        dlList.insert(0,x[1])
    elif x[0] == 'delete':
        if x[1] in dlList:
            dlList.remove(x[1])
        else :
            pass
    elif x[0] == 'deleteFirst':
        dlList.pop(0)
    elif x[0] == 'deleteLast':
        dlList.pop()
    else:
        pass

print(dlList.pop(0),end="")
for x in dlList:
    print(" "+x,end="")
print()

### FIXED CODE ###

import sys
from collections import deque
input_lines = sys.stdin.readlines()

doublyLinkedList = deque()


for x in input_lines[1:]:
    oneLine = x.split()
    if 'insert' in oneLine[0]:
        doublyLinkedList.appendleft((int)(oneLine[1]))
    elif 'delete' == oneLine[0]:
        remove_value = (int)(oneLine[1])
        if remove_value in doublyLinkedList:
            doublyLinkedList.remove(remove_value)
    elif 'deleteFirst'in oneLine[0]:
        doublyLinkedList.popleft()
    elif 'deleteLast' in oneLine[0]:
        doublyLinkedList.pop()

print(*doublyLinkedList)
### BUGGY CODE ###

def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    for i, a in enumerate(a_s[:-1]):
        dp[i + 1][0] = s = dp[i][0]
        for j in range(1, a + 1):
            dp[i + 1][j] = s = s + dp[i][j]
        for j in range(a + 1, k + 1):
            dp[i + 1][j] = s = s + dp[i][j] - dp[i][j - a - 1]
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

N = int(input())
lis = list(map(int,input().split()))
for i in range(1,N+1):
    print(lis.index(i) + 1 ,end=" ")

### FIXED CODE ###

N = int(input())
lis = list(map(int,input().split()))
dic = {}
for i,popu in zip(range(1,N+1),lis):
    dic[popu] = i
for j in range(1,N+1):
    print(dic[j],end = " ")
### BUGGY CODE ###

from collections import *
from bisect import *

N, Q = map(int,input().split())
C = list(map(int,input().split()))

d = defaultdict(list)

for i,c in enumerate(C):
    d[c]+=[i]

for _ in range(Q):
    l, r = map(int,input().split())
    print(sum(bisect(L, r-1)-bisect_left(L, l-1) > 0 for L in d.values()))

### FIXED CODE ###

import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  #対象のリスト
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()
### BUGGY CODE ###

# D - Partition
# Mの約数で、しかもN倍してもMを超えないもののうち、最大のものを探す

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

if N == 1:
    print(M)
    exit()

x = 1
while x * N <= M:
    if M % x == 0:
        ans = x
    x += 1
    
print(ans)

### FIXED CODE ###

# D - Partition
# Mの約数で、しかもN倍してもMを超えないもののうち、最大のものを探す

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

if N == 1:
    print(M)
    exit()

x = M//N

while 1:
    if M % x == 0:
        ans = x
        break
    x -= 1
    
print(ans)
### BUGGY CODE ###

N=int(input())
X=list(map(int,input().split()))
list=sorted(X)

for i in X:
    if list.index(i)<N/2:
        print(list[N//2])
    else:
        print(list[N//2-1])

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
list=sorted(X)

for i in range(N):
    if list[int((N/2))]<=X[i]:
        print(list[int(N/2)-1])
    else:
        print(list[int(N/2)])
### BUGGY CODE ###

n = int(input())
s = input()
a = s.count("R")
b = s.count("G")
c = s.count("B")
x = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i]==s[j]:
      continue
    else:
      if 2*j-i<= n-1 and len({s[i], s[j], s[2*j-i]})==3:
        x += 1
print(a*b*c-x)


### FIXED CODE ###

n = int(input())
s = input()
a = s.count("R")
b = s.count("G")
c = s.count("B")
z = a*b*c
R=[]
G=[]
B=[]
for i in range(n):
  if s[i]=="R":
    R.append(i)
  elif s[i]=="G":
    G.append(i)
  else:
    B.append(i)
x = 0
for i in R:
  for j in G:
    if 0 <= 2*j-i <= n-1 and s[2*j-i]=="B":
      x+=1
    if 0 <= 2*i-j <= n-1 and s[2*i-j]=="B":
      x+=1
    if (i+j)%2==0 and s[(i+j)//2]=="B":
      x+=1
print(z-x)
### BUGGY CODE ###

N = int(input())
S = []
length = 0

for _ in range(N):
    s = [v for v in input()]
    s.sort()

    hit = 0
    for i in range(length):
        t, num = S[i]
        if s == t:
            S[i] = (t, num + 1)
            hit = 1
            break
    if hit == 0:
        S.append((s, 1))
        length += 1

ans = 0
for i in range(length):
    t, num = S[i]
    ans += (num * (num - 1)) // 2
print(ans)

### FIXED CODE ###

N = int(input())
dic = {}
ans = 0
for i in range(N):
    s = [v for v in input()]
    s.sort()
    word = ''.join(s)    

    if word in dic:
        dic[word] += 1
    else:
        dic[word] = 1

for word in dic:
    num = dic[word]
    ans += (num * (num - 1)) // 2

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

n,m = map(int,input().split())
a,b = [0 for _ in range(n)],[0 for _ in range(n)]

for i in range(n):
    a[i],b[i] = map(int,input().split())

bought = 0
ans = 0
if len(a) == 1:
    print(a[0]*m)
    exit()
while(bought <= m):
    remain = m - bought
    if b[a.index(min(a))] <= remain:
        ans += min(a)*b[a.index(min(a))]
        bought += b[a.index(min(a))]
        b.remove(b[a.index(min(a))])
        a.remove(min(a))
    else:
        ans += min(a)*remain
        break
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort(key = lambda a:a[0])
bought = 0
price = 0
for i in range(n):
    remain = m - bought
    if a[i][1] < remain:
        bought += a[i][1]
        price += a[i][0] * a[i][1]
    else:
        price += a[i][0]*remain
        print(price)
        exit()
### BUGGY CODE ###

n, a, b = map(int, input().split())
c = 0

if a == 0:
    print(int(0))
else:
    while n >= 0:
        if n >= a:
            n -= a
            c += 1
        else:
            print(a*c + n)
            break
        if n >= b:
            n -= b
        else:
            print(a*c)
            break



### FIXED CODE ###

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

ans = n // (a+b) * a
rem = n % (a+b)

ans += min(rem, a)
print(ans)
### BUGGY CODE ###

class BIT:
	"0-indexed apparently"
	
	def __init__(self, n):
		self.n = n
		self.data = [0] * (n+1)
		
	def point_add(self, index, value):
		index += 1
		while index <= self.n:
			self.data[index] += value
			index += index & -index
		
	def folded(self, r):
		"[0, r)"
		ret = 0
		while r > 0:
			ret += self.data[r]
			r -= r & -r
		return ret
		
	def bisect_left(self, value):
		index = 0
		k = 1 << ((self.n + 1).bit_length() - 1)
		while k > 0:
			if index + k <= self.n and self.data[index + k] < value:
				value -= self.data[index + k]
				index += k
			k >>= 1
		return index + 1
		
N = int(input())
As = list(map(int, input().split()))

A_inv = [0] * N
for i, A in enumerate(As):
	A_inv[A-1] = i
	
bit = BIT(N + 2)
bit.point_add(0, 1)
bit.point_add(N+1, 1)
ans = 0
for A, index in enumerate(A_inv):
	A += 1
	index += 1
	v = bit.folded(index)
	ans += A * (bit.bisect_left(v+1) - index - 1) * (index - bit.bisect_left(v) + 1)
	#print(A, ans)
	bit.point_add(index, 1)
	
print(ans)

### FIXED CODE ###

class BIT:
	"0-indexed apparently"
	
	def __init__(self, n):
		self.n = n
		self.data = [0] * (n+1)
		
	def point_add(self, index, value):
		index += 1
		while index <= self.n:
			self.data[index] += value
			index += index & -index
		
	def folded(self, r):
		"[0, r)"
		ret = 0
		while r > 0:
			ret += self.data[r]
			r -= r & -r
		return ret
		
	def bisect_left(self, value):
		index = 0
		k = 1 << ((self.n + 1).bit_length() - 1)
		while k > 0:
			if index + k <= self.n and self.data[index + k] < value:
				value -= self.data[index + k]
				index += k
			k >>= 1
		return index + 1
		
N = int(input())
As = list(map(int, input().split()))

A_inv = [0] * N
for i, A in enumerate(As):
	A_inv[A-1] = i
	
bit = BIT(N + 2)
bit.point_add(0, 1)
bit.point_add(N+1, 1)
ans = 0
for A, index in enumerate(A_inv):
	A += 1
	index += 1
	v = bit.folded(index)
	ans += A * (bit.bisect_left(v+1) - index - 1) * (index - bit.bisect_left(v) + 1)
	#print(A, ans)
	bit.point_add(index, 1)
	
print(ans)
### BUGGY CODE ###

from collections import deque


def main():
    height, width = map(int, input().split())
    q = deque([])
    grid = []
    change_time = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        now = list(input())
        for j in range(width):
            if now[j] == "#":
                q.append([i, j])
                change_time[i][j] = 0
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x = q.popleft()
        grid[y][x] = "#"
        answer = change_time[y][x]
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                change_time[new_y][new_x] = change_time[y][x] + 1
                q.append([new_y, new_x])
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [stdin.readline() for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and distance[new_y][new_x] < 0:
                distance[new_y][new_x] = answer + 1
                q.append((new_y, new_x))
    print(answer)


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

import bisect
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
    if all(L % L2 != 0 for L2 in lst1):
        lst1.append(L)

lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)

### FIXED CODE ###

import bisect, math
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
  f = 0
  for d in range(3, math.floor(math.sqrt(L))+1, 2):
    if L % d == 0:
      f = 1
      break
  if f == 0:
    lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)