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

import sys
#大きすぎるとダメ
sys.setrecursionlimit(2600)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(map(int,input().split()))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    ans += L//a
  print(ans%MOD)

if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

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

n=int(input())
a=list(map(int,input().split()))
s=1
for i in range(n):
  s*=a[i]
cnt=0
while s%2==0:
  s//=2
  cnt+=1

print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
  while a[i]%2==0:
    a[i]//=2
    cnt+=1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1]*(10**6+1)
for i in range(n):
    if ls[a[i]] == 1:
        for j in range(a[i]*2, 10**6+1, a[i]):
            ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and a.count(a[i]) <= 1:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1] * (10 ** 6 + 1)
cnt = [0] * (10 ** 6 + 1)
for i in range(n):
    cnt[a[i]] += 1
    if cnt[a[i]] == 1:
        if ls[a[i]] == 1:
            for j in range(a[i] * 2, 10 ** 6 + 1, a[i]):
                ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and cnt[a[i]] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if (0 <= z <= k) and type(z) == int:
            cnt += 1
            
print(cnt)

### FIXED CODE ###

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

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

# In[84]:


S = input() + " "


# In[85]:


ans = [0]*(len(S)+1)
for i in range(len(S)):
    count_left = 0
    count_right = 0
    for j in range(i):
        if S[i-j-1] == "<":
            count_left += 1
        else:
            j -= 1
            break
    for k in range(i,len(S)):
        if S[k] == ">":
            count_right += 1
        else:
            k -= 1
            break
    ans[i] = max(count_left, count_right)
#     print(count_left, count_right)
#     print(S[i-j-1:i], S[i:k+1])
# print(ans)
print(sum(ans))


# In[ ]:






### FIXED CODE ###

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

# In[86]:


# ans = [0]*(len(S)+1)
# for i in range(len(S)):
#     count_left = 0
#     count_right = 0
#     for j in range(i):
#         if S[i-j-1] == "<":
#             count_left += 1
#         else:
#             j -= 1
#             break
#     for k in range(i,len(S)):
#         if S[k] == ">":
#             count_right += 1
#         else:
#             k -= 1
#             break
#     ans[i] = max(count_left, count_right)
# #     print(count_left, count_right)
# #     print(S[i-j-1:i], S[i:k+1])
# # print(ans)
# print(sum(ans))


# In[87]:


from collections import deque
S = input()
left = deque([0])
right = deque([0])
cnt = 0
for s in S:
    if s == '<':
        cnt += 1
    else:
        cnt = 0
    left.append(cnt)
cnt = 0
for s in S[::-1]:
    if s == '>':
        cnt += 1
    else:
        cnt = 0
    right.appendleft(cnt)
ans = 0
for l, r in zip(left, right):
    ans += max(l, r)
print(ans)


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

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N * 0.999 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
k = min(n - 1, k)
h = list(map(int, input().split()))
cost = [0 for _ in range(k)]
for i in range(1, n):
    (cs, hs) = (k - i, 0) if k > i else (0, i - k)
    new_cost = min([ck + abs(h[i] - hk) for ck, hk in zip(cost[cs:], h[hs:])])
    cost = cost[1:] + [new_cost]
print(cost[k - 1])


### FIXED CODE ###

n, k = map(int, input().split())
k = min(n - 1, k)
h = list(map(int, input().split()))
cost = [0 for _ in range(n)]
for i, hi in enumerate(h):
    if i == 0: continue
    st = i - k if i > k else 0
    cost[i] = min([ck + abs(hi - hk) for ck, hk in zip(cost[st:i], h[st:i])])
print(cost[-1])
### BUGGY CODE ###

from functools import reduce
from operator import mul
import sys
input = sys.stdin.readline

count = int(input())
list = list(map(int, input().split()))
sum = reduce(mul, list)

if sum > 1000000000000000000:
    sum = -1

print(sum)

### FIXED CODE ###

from functools import reduce
from operator import mul
import sys
input = sys.stdin.readline

count = int(input())
list = list(map(int, input().split()))
sum = list[0]
if 0 in list:
    print(0)
    exit()
else:
    for i in range(count - 1):
        sum = sum * list[i + 1]
        if sum > 1000000000000000000:
            print(-1)
            exit()


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

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

in_ = set()
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    in_.add(b)

dist = [-1]*n

from collections import deque
def dfs(cur):
    que = deque()
    que.append((cur, 0))
    while que:
        cur, d = que.pop()
        if dist[cur] > d:
            continue
        dist[cur] = d
        for to in G[cur]:
            if dist[to] < d+1:
                que.append((to, d+1))

for i in range(n):
    if i in in_:
        continue
    dfs(i)

ans = max(dist)

print(ans)

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)

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

in_ = set()
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    in_.add(b)

dist = [-1]*n

from collections import deque
def dfs(cur):
    if dist[cur] != -1:
        return dist[cur]
    r = 0
    for to in G[cur]:
        r = max(r, dfs(to)+1)
    dist[cur] = r
    return r

for i in range(n):
    if i in in_:
        continue
    dfs(i)

ans = max(dist)

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

N = int(input())
S = input()
outCount = 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if S[i]==S[j] or S[j]==S[k] or S[i]==S[k]:
                continue
            elif j-i == k-j:
                continue
            elif i<j<k:
                outCount += 1
print(outCount)

### FIXED CODE ###

N = int(input())
S = input()
noCount = {'R': 0, 'G': 0, 'B': 0}
minusCount = 0
for i in S:
    if i == 'R':
        noCount['R'] += 1
    elif i == 'G':
        noCount['G'] += 1
    elif i == 'B':
        noCount['B'] += 1
RGB = noCount['R']*noCount['G']*noCount['B']

for step in range(1, (N+1)//2):
    for cenPos in range(step, N-step):
        if S[cenPos - step] != S[cenPos] and S[cenPos] != S[cenPos + step] and S[cenPos - step] != S[cenPos + step]:
            minusCount += 1
print(RGB - minusCount)
### BUGGY CODE ###

from fractions import gcd
K = int(input())

def gcd3(a, b, c):
  x = gcd(a, b)
  y = gcd(x, c)
  return y

ans = 0
#count = 0
for i in range(1, K + 1):
  for j in range(i, K + 1):
    for k in range(j, K + 1):
      #count += 1
      #print(count, gcd3(i, j, k))
      x = gcd3(i, j, k)
      if i == j:
        if j == k:
          ans += x
        else:
          ans += 3 * x
      else:
        if i == k:
          ans += 3 * x
        elif j == k:
          ans += 3 * x
        else:
          ans += 6 * x
          

print(ans)  


### FIXED CODE ###

import math
from functools import reduce
K = int(input())

def gcd(*numbers):
  return reduce(math.gcd, numbers)


ans = 0
#count = 0
for i in range(1, K + 1):
  for j in range(i, K + 1):
    for k in range(j, K + 1):
      #count += 1
      #print(count, gcd3(i, j, k))
      x = gcd(i, j, k)
      if i == j:
        if j == k:
          ans += x
        else:
          ans += 3 * x
      else:
        if i == k:
          ans += 3 * x
        elif j == k:
          ans += 3 * x
        else:
          ans += 6 * x
          

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

n = int(input())
a = list(map(int, input().split()))
A = []
cnt = 0

for i in range(n-1):
    A.append(a[i])
    if sum(A) > 0:
        while sum(A) + a[i+1] >= 0:
            a[i+1] -= 1
            cnt += 1

    elif sum(A) < 0:
        while sum(A) + a[i+1] <= 0:
            a[i+1] += 1
            cnt += 1
            
if sum(a) == 0:
    cnt += 1

print(cnt)

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

s=input()
q=int(input())

a=0
for i in range(q):
  t=input()
  if t=='1':
    a=a^1
  else:
    t, f, c = map(str, t.split())
    f=int(f)
    if (f^a)&1==0:
      s=s+c
    else:
      s=c+s
if a==1:
  s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
head=''
foot=''

a=0
for i in range(q):
  t=input()
  if t=='1':
    a=a^1
  else:
    t, f, c = map(str, t.split())
    f=int(f)
    if (f^a)&1==0:
      foot+=c
    else:
      head=c+head
s=head+s+foot
if a==1:
  s=s[::-1]
print(s)
### BUGGY CODE ###

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

dp = [1,1]
temp = 1
if 1 in a: dp[1] = 0
  
for i in range(2,n+1):
  if i in a: dp.append(0)
  else: dp.append(dp[i-1] + dp[i-2])

print(dp[n]%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
 
dp = [0, 1]
for i in range(N):
    if i+1 in A: dp.append(0)
    else: dp.append(dp[i]+dp[i+1])
print(dp[N+1]%1000000007)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
A = [n for n in a]

cnt1 = 0
cnt2 = 0
S = 0

if a[0] > 0:
    for i in range(n-1):
        S += a[i]
        if a[i] > 0:
            while S + a[i+1] >= 0:
                a[i+1] -= 1
                cnt1 += 1
        elif a[i] < 0:
            while S + a[i+1] <= 0:
                a[i+1] += 1
                cnt1 += 1
    A[0] = -1
    cnt2 = a[0] + 1
    for i in range(n-1):
        S += A[i]
        if A[i] > 0:
            while S + A[i+1] >= 0:
                A[i+1] -= 1
                cnt2 += 1
        elif A[i] < 0:
            while S + A[i+1] <= 0:
                A[i+1] += 1
                cnt2 += 1
elif a[0] < 0:
    for i in range(n-1):
        S += a[i]
        if a[i] > 0:
            while S + a[i+1] >= 0:
                a[i+1] -= 1
                cnt1 += 1
        elif a[i] < 0:
            while S + a[i+1] <= 0:
                a[i+1] += 1
                cnt1 += 1
    A[0] = 1
    cnt2 = -a[0] + 1
    for i in range(n-1):
        S += A[i]
        if A[i] > 0:
            while S + A[i+1] >= 0:
                A[i+1] -= 1
                cnt2 += 1
        elif A[i] < 0:
            while S + A[i+1] <= 0:
                A[i+1] += 1
                cnt2 += 1
else:
    a[0] = 1
    cnt1 = 1
    for i in range(n-1):
        S += a[i]
        if a[i] > 0:
            while S + a[i+1] >= 0:
                a[i+1] -= 1
                cnt1 += 1
        elif a[i] < 0:
            while S + a[i+1] <= 0:
                a[i+1] += 1
                cnt1 += 1
    A[0] = -1
    cnt2 = 1
    for i in range(n-1):
        S += A[i]
        if A[i] > 0:
            while S + A[i+1] >= 0:
                A[i+1] -= 1
                cnt2 += 1
        elif A[i] < 0:
            while S + A[i+1] <= 0:
                A[i+1] += 1
                cnt2 += 1
cnt = cnt2 if cnt1 >= cnt2 else cnt1

print(cnt)


### FIXED CODE ###

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

S1 = 0
S2 = 0
#S1が奇数番目が正の場合、S2が偶数番目が負の場合
cnt1 = 0
cnt2 = 0

for i,num in enumerate(a):
    S1 += num
    if i % 2 == 0 and S1 <= 0:
        cnt1 += 1 - S1
        S1 = 1
    if i % 2 != 0 and S1 >= 0:
        cnt1 += 1 + S1
        S1 = -1

    S2 += num
    if i % 2 == 0 and S2 >= 0:
        cnt2 += 1 + S2
        S2 = -1
    if i % 2 != 0 and S2 <= 0:
        cnt2 += 1 - S2
        S2 = 1

print(cnt1 if cnt1 <= cnt2 else cnt2)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
data=[[int(i) for i in input().split()] for i in range(m)]
data.sort(key=lambda x:x[1])
data.reverse()
a.sort()
a.reverse()
ans=0
flag=True
for i in range(n):
  if flag==True:
    if data[0][1]<a[0]:
      ans+=a[0]
      a=a[1:]
    else:
      ans+=data[0][1]
      data[0][0]-=1
      if data[0][0]==0:
        if len(data)>1:
          data=data[1:]
        else:
          flag=False
  else:
    ans+=a[0]
    a=a[1:]
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[[1,int(i)] for i in input().split()]
data=[[int(i) for i in input().split()] for i in range(m)]
data.extend(a)
data.sort(key=lambda x:x[1],reverse=True)
ans=0
flag=True
index=0
while n>0:
  tmp=min(data[index][0],n)
  ans+=data[index][1]*tmp
  n-=tmp
  index+=1
print(ans)
### BUGGY CODE ###

from itertools import permutations
import sys


input = sys.stdin.readline


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

dest = [x-1 for x in map(int, input().split())]


inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    mat[a-1][b-1] = mat[b-1][a-1] = c


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


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
        if tmp > ans:
            break
    ans = min(ans, tmp)

print(ans)


### FIXED CODE ###

from itertools import permutations
import sys


input = sys.stdin.readline


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

dest = [x-1 for x in map(int, input().split())]


inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    mat[a-1][b-1] = mat[b-1][a-1] = c


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


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
    ans = min(ans, tmp)

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

n=int(input())
a=list(map(int, input().split())) 
ans = 0
ru = []

for i in range(n):
    ru.append(int(i+a[i]))
    tmp = i - a[i]
    ans += ru.count(tmp)

print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split())) 
ans = 0
ru = []

for i in range(n):
    ru.append(int(i + 1 + a[i]))

c = collections.Counter(ru)
#print(c)

for i in range(n):
    tmp = i + 1 - a[i]
    ans += c[tmp]

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

from collections import defaultdict,Counter
import queue

N, X, Y = map(int, input().split())
d = defaultdict(list)
d[X].append(Y)
d[Y].append(X)
for i in range(1,N):
    d[i].append(i+1)
    d[i+1].append(i)

ans=defaultdict(int)

for i in range(N):
    dist = [None]*N
    s=i+1
    q=queue.Queue()
    q.put(s)
    dist[i]=0

    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == None:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    c=Counter(dist)
    for i,m in c.items():
        ans[i]+=m


for i in range(1,N):
    print(ans[i]//2)

### FIXED CODE ###

from collections import Counter, deque


def bfs(d, s, N):
    dist = [-1]*N
    q = deque()
    q.append(s)
    dist[i] = 0
    while len(q) != 0:
        From = q.popleft()
        for To in d[From]:
            if dist[To-1] == -1:
                q.append(To)
                dist[To-1] = dist[From-1]+1
    return dist


N, X, Y = map(int, input().split())
d = [[] for _ in range(N+1)]
d[X].append(Y)
d[Y].append(X)
for i in range(1, N):
    d[i].append(i+1)
    d[i+1].append(i)

ans = [0]*(N+1)

for i in range(N):
    s = i+1
    c = Counter(bfs(d, i+1, N))
    for i, m in c.items():
        ans[i] += m

for i in range(1, N):
    print(ans[i]//2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
Bs = []
for i in range(Q):
    Bs.append(list(map(int, input().split(' '))))
    
    
A_list = [0]*(10**5+1)
for i in A:
    A_list[i] += 1
    
for B in Bs:
    b, c = B
    A_list[c] += A_list[b]
    A_list[b] = 0
    print(sum([i*num for num, i in enumerate(A_list)]))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
Bs = []
for i in range(Q):
    Bs.append(list(map(int, input().split(' '))))
    
    
A_list = [0]*(10**5+1)
for i in A:
    A_list[i] += 1
    
sum_value = sum(A)
for B in Bs:
    b, c = B
    sum_value += A_list[b]*c
    sum_value -= A_list[b]*b
    
    A_list[c] += A_list[b]
    A_list[b] = 0
    print(sum_value)
### BUGGY CODE ###

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

from collections import Counter

c = Counter(A)
cnt = 0

if len(c) > K:
    for i in range(K, len(c)):
        cnt += c.most_common()[i][1]
        
print(cnt)

### FIXED CODE ###

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

from collections import Counter

ac = Counter(A)

cnt = 0

if len(ac) > K:
    for a in ac.most_common()[K:]:
        cnt += a[1]
    
print(cnt)
### BUGGY CODE ###

N = int(input())
line = input()

ans = N
for i in range(N):
 west = line[:i]
 tmp = west.count('W')
 east = line[i+1:]
 tmp += east.count('E')
 if ans>tmp:
  ans = tmp


print(ans)

### FIXED CODE ###

N = int(input())
line = input()

ans = line[1:N].count('E')
tmp = ans
for i in range(1,N):
 if line[i] == 'E':
  tmp -= 1
 if line[i-1] == 'W':
  tmp += 1
 if ans>tmp:
  ans = tmp

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

N = int(input())
L0 = list(map(int, input().split()))
L = sorted(L0)
tri = 0
for left in range(N-2):
    for mid in range(left+1, N-1):
        right = mid+1
        while right <= N-1 and L[right] < L[left] + L[mid]:
            tri += 1
            right += 1

print(tri)

### FIXED CODE ###

import bisect
N = int(input())
L0 = list(map(int, input().split()))
L = sorted(L0)
tri = 0
for left in range(N-2):
    for mid in range(left+1, N-1):
        x = bisect.bisect_left(L, L[left]+L[mid])
        tri += x - mid - 1

print(tri)
### BUGGY CODE ###

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

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
	tergets = []
	for i in marix:
		if (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				tergets.append(i)
				
	ans = []
	for i in maps:
		l, r = i
		counts1 = 0
		counts2 = 0
		for j in tergets:
			if j < l:
				counts1 += 1
				counts2 += 1
				continue
			if j <= r:
				#print(marix)
				counts2 += 1
		print(counts2 - counts1)
				
	
	
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()