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

# numpyとか使って高速化お遊び
import sys
import numpy as np

def main():
    inf = 10 ** 7
    s = sys.stdin.readline()[:-1]
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    # 次をその文字にした時の「長さ、位置」
    size = np.zeros(26, "i8")
    pos = [n + i for i in range(26)]
    # 解答復元のための移動先
    nxt = [-1] * n
    # 後ろの文字から順に見る
    for i in range(n - 1, -1, -1):
        # 次をどの文字にすれば短くなるか調べる
        # 同じ長さの時は辞書順優先
        # codeはaを0として番号化したもの
        min_size_code = size.argmin()
        now_code = ord(s[i]) - 97
        size[now_code] = size[min_size_code] + 1
        pos[now_code] = i
        nxt[i] = pos[min_size_code]
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    # 最短になる最初の文字を調べて、nxtの順にたどる
    min_size_code = size.argmin()
    i = pos[min_size_code]
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 7
    s = input()
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    # 次をその文字にした時の「長さ、位置」
    size = [0] * 26
    pos = [n + i for i in range(26)]
    # 解答復元のための移動先
    nxt = [-1] * n
    # 後ろの文字から順に見る
    for i in range(n - 1, -1, -1):
        min_size = inf
        min_pos = -1
        # 次をどの文字にすれば短くなるか調べる
        # 同じ長さの時は辞書順優先
        for sz, p in zip(size, pos):
            if sz < min_size:
                min_size = sz
                min_pos = p
        code = ord(s[i]) - 97
        size[code] = min_size + 1
        pos[code] = i
        nxt[i] = min_pos
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    # 最短になる最初の文字を調べて、nxtの順にたどる
    min_size = inf
    min_pos = -1
    for sz, p in zip(size, pos):
        if sz < min_size:
            min_size = sz
            min_pos = p
    i = min_pos
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()
### BUGGY CODE ###

S = str(input())


def main(S):
    a = len(S)
    b = list(0 for j in range(4, a+1)
        for i in range(a-j+1)
            if int(S[i:i+j])%2019==0)
    print(len(b))
if __name__ == '__main__':
    main(S)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import re

white = re.compile('(1*)$')
black = re.compile('(0*)$')

while True:

    n = int(raw_input())

    if n == 0:
        break

    s = ''
    for i in xrange(n):
        if (i + 1) % 2 != 0:
            s += raw_input()

        else:
            p = raw_input()
            if p == '0':
                m = white.search(s)
                s = white.sub('0' * len(m.group(1)), s)
                s += '0'
            else:
                m = black.search(s)
                s = black.sub('1' * len(m.group(1)), s)
                s += '1'
    print s.count('0')

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    li = []

    for i in xrange(n):
        p = int(raw_input())
        if i == 0:
            li.append([p, 1])
            continue
        # odd
        if i % 2 == 0:
            if li[-1][0] == p:
                li[-1][1] += 1
            else:
                li.append([p, 1])
        else:
            if li[-1][0] == p:
                li[-1][1] += 1
            else:
                li[-1][0] = p
                li[-1][1] += 1
                if len(li) >= 2 and li[-2][0] == li[-1][0]:
                    li[-2][1] += li[-1][1]
                    del li[-1]

    print sum(t[1] for t in li if t[0] == 0)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:

    ans*=i
if ans>10**18:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if min(a)==0:
    print(0)
    exit()
for i in a:
    ans*=i
    if ans>10**18:
        print(-1)
        exit()
if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split(' '))
s = [list(map(int, input().split(' '))) for _ in range(m)]
set_s = []
result = [n*(n-1)/2]
for i in range(m-1, 0, -1):
    x = set()
    y = set()
    j = 0
    check = 0
    while j < len(set_s):
        if set(s[i]) <= set_s[j]:
            result.append(result[-1])
            check = 1
            break
        elif {s[i][0]} <= set(set_s[j]):
            x = set_s.pop(j)
            j = 0
        elif {s[i][1]} <= set(set_s[j]):
            y = set_s.pop(j)
            j = 0
        else:
            j += 1
    if len(x) != 0 and len(y) != 0:
        result.append(result[-1]-len(x)*len(y))
        set_s.append(x|y)
    elif len(x) != 0:
        result.append(result[-1]-len(x))
        set_s.append(x|{s[i][1]})
    elif len(y) != 0:
        result.append(result[-1]-len(y))
        set_s.append(y|{s[i][0]})
    elif check == 0:
        set_s.append(set(s[i]))
        result.append(result[-1]-1)
for i in result[::-1]:
    print(int(i))

### FIXED CODE ###

n, m = map(int, input().split(' '))
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = list(map(int, input().split(' ')))

c = [-1]*(m+2)

def find(num):
    if c[num] < 0:
        return num
    else:
        k = find(c[num])
        c[num] = k
        return k

result = [int(n*(n-1)/2)]
for i in range(m-1, 0,-1):
    x = find(a[i])
    y = find(b[i])

    if x != y:
        result.append(result[-1]-c[x]*c[y])
        x, y = sorted([x,y])
        c[x] += c[y]
        c[y] = x
    else:
        result.append(result[-1])

for i in result[::-1]:
    print(int(i))
### BUGGY CODE ###

n = int(input())
s = input()
point = 0

# ラッキーナンバーを全探索する
for i in range(1000):
    t = str(i).zfill(3)
    now = 0
    # sでラッキーナンバーが作れるかを検証
    for j in s:
        if j == t[now]:
            now += 1
        if now == 3:
            point += 1
            break

print(point)

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

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

n, q = map(int, input().split())
s = input()
li = []

for i in range(q):
    l, r = map(int, input().split())
    li.append(s[l-1:r].count("AC"))

for i in li:
    print(i)

### FIXED CODE ###

import bisect
n, q = map(int, input().split())
s = input()
li = []

for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        li.append(i)

ans = []
num = 0

for i in range(q):
    l, r = map(int, input().split())
    num = bisect.bisect_right(li, r-2)-bisect.bisect_left(li, l-1)
    ans.append(num)

for i in ans:
    print(i)
### BUGGY CODE ###

n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def union(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.union(P[i][0], P[i][1])
  
for i in range(l):
  rail.union(R[i][0], R[i][1])

road.union = road.get_union()
rail.union = rail.get_union()

for e in range(1, n+1):
  print(len(road.union[road.root(e)] & rail.union[rail.root(e)]), end=' ')
  

### FIXED CODE ###

n, k, l = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(k)]
R = [[int(i) for i in input().split()] for j in range(l)]

class UnionFind():
  def __init__(self, elements):
    self.elements = elements
    self._root = {}
    for e in self.elements:
      self._root[e] = e
    
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if not x == y:
      self._root[x] = y
    
  def root(self, x):
    if not self._root[x] == x:
      self._root[x] = self.root(self._root[x])
    return self._root[x]
  
  def count(self):
    cnt = {}
    for e in self.elements:
      cnt[self.root(e)] += cnt.get(self.root(e), 0)
      
    for e in self.elements:
      yield cnt.get(e, 0)
      
  def get_union(self):
    union = {}
    for e in self.elements:
      if self.root(e) in union:
        union[self.root(e)].add(e)
      else:
        union[self.root(e)] = {e}
    return union
      
  
road = UnionFind(range(1, n+1))
rail = UnionFind(range(1, n+1))

for i in range(k):
  road.unite(P[i][0], P[i][1])
  
for i in range(l):
  rail.unite(R[i][0], R[i][1])

ans = {}
key = []
for e in range(1, n+1):
  key.append((road.root(e), rail.root(e)))
  ans[key[-1]] = ans.get(key[-1], 0) +1
  
for k in key:
  print(ans[k], end=' ')
### BUGGY CODE ###

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

tmp = 0
a = 0
for i in range(B - 1, N + 1, B):
    if (s := (A * i) // B - A * a) > 0:
        tmp = max(s, tmp)
        a += 1
    else:
        break
    
for i in range(N, N - N % B - 1, -1):
    if (s := (A * i) // B - A * (i // B)) > 0:
        tmp = max(s, tmp)
    else:
        break

print(tmp)



### FIXED CODE ###

global A, B
A, B, N = map(int, input().split())

def f(num):
    return(A * num) // B - A * (num // B)

print(f(min(B - 1, N)))
### BUGGY CODE ###

#import functools

def main():
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    A.sort(reverse=True)

    if A[-1] == 0:
        print('0')
        exit()
    elif A[0] > 1e18:
        print('-1')
        exit()

    ret = 1
    for x in A:
        ret = ret * x
        # if ret > 1e18:
        #     print('-1')
        #     exit()
        # elif ret == 0:
        #     print('0')
        #     exit()

    if ret == 0:
        print('0')
        exit()
    elif ret > 1e18:
        print('-1')
        exit()
    print(f'{ret}')


if __name__ == "__main__":
    main()

### FIXED CODE ###

#import functools

def main():
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    A.sort(reverse=True)

    if A[-1] == 0:
        print('0')
        exit()
    elif A[0] > 1e18:
        print('-1')
        exit()

    ret = 1
    for x in A:
        ret = ret * x
        if ret > 1e18:
            print('-1')
            exit()
        elif ret == 0:
            print('0')
            exit()

    if ret == 0:
        print('0')
        exit()
    elif ret > 1e18:
        print('-1')
        exit()
    print(f'{ret}')


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

s=input()
t=input()

jisho={}
alphabets = [chr(ord('a') + i) for i in range(26)]
for moji in alphabets:
    jisho[moji] = [i for i,x in enumerate(s) if x==moji]

lis = [jisho[moji] for moji in t]
if [] in lis:
    print(-1)
else:    
    old=-1
    count=0
    for i,cand in enumerate(lis):
        tes = [temp for temp in cand if temp>old]
        if len(tes)==0:
            num = min(cand)
        else:
            num = min(tes)
        if num<=old: count+=1
        old=num
    print(count*len(s)+old+1)

### FIXED CODE ###

import bisect
s=input()
t=input()
jisho={}
alphabets = [chr(ord('a') + i) for i in range(26)]
for moji in alphabets:
    jisho[moji] = [i for i,x in enumerate(s) if x==moji]
lis = [jisho[moji] for moji in t]

if [] in lis:
    print(-1)
else:    
    old=-1
    count=0
    for cand in lis:
        z=bisect.bisect(cand,old)
        if z==len(cand):
            num=min(cand)
        else:
            num=cand[z]
#         tes = [temp for temp in cand if temp>old]
#         if len(tes)==0:
#             num = min(cand)
#         else:
#             num = min(tes)
        if num<=old: count+=1
        old=num
    print(count*len(s)+old+1)
### BUGGY CODE ###

#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""
# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7

def main():
  n = int(input())
  LIST = readInts()
  LIST = sorted(LIST)
  ans = 1
  pr_ = LIST[0]
  for i in range(1,n):
    cnt = 1
    for j in range(i,n):
      if abs(pr_ - LIST[j]) <= 2:
        cnt += 1
      else:
        ans = max(ans,cnt)
    pr_ = LIST[i]
  print(ans)
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""
# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7

def main():
  n = int(input())
  LIST = readInts()
  MAX_ = [0] * (10**5 + 10) # 始めに確保しておく
  for a in LIST:
    for i in range(3):
      MAX_[a+i]+=1 # -1,0,1のように、0,1,2で被るものを考える。
  print(max(MAX_))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

MOD = 10**9 + 7
def main():
    n, m = map(int, input().split())
    s = list(map(int, input().split()))
    t = list(map(int, input().split()))
    dp = [[0]*(m+1) for _ in range(n+1)]
    for si in range(1, n+1):
        for ti in range(1, m+1):
            if s[si-1] == t[ti-1]:
                dp[si][ti] += 1
                dp[si][ti] += dp[si-1][ti-1]
            dp[si][ti] += dp[si-1][ti] + dp[si][ti-1]
            dp[si][ti] -= dp[si-1][ti-1]
            dp[si][ti] %= MOD
    print(dp[n][m] + 1)
#    for i in range(n+1):
#        print(dp[i])

if __name__ == "__main__":
    main()

### FIXED CODE ###

MOD = 10**9 + 7
def main():
    n, m = map(int, input().split())
    s = list(map(int, input().split()))
    t = list(map(int, input().split()))
    dp = [[0]*(m+1) for _ in range(n+1)]
    for si in range(1, n+1):
        for ti in range(1, m+1):
            if s[si-1] == t[ti-1]:
                dp[si][ti] += 1
                dp[si][ti] += dp[si-1][ti-1]
            dp[si][ti] += dp[si-1][ti] + dp[si][ti-1]
            dp[si][ti] -= dp[si-1][ti-1]
            dp[si][ti] %= MOD
    print(dp[n][m] + 1)
#    for i in range(n+1):
#        print(dp[i])

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

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


class UnionFind():
    def __init__(self, n):
        self.tree = [i for i in range(n)]

    def root(self, x):
        if(self.tree[x] == x):
            return x
        self.tree[x] = self.root(self.tree[x])
        return self.tree[x]  # 経路圧縮

    def same(self, x, y):  # xとyが同じ木に属するか
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if(x == y):
            return
        self.tree[x] = y


uf = UnionFind(n)
uf2 = UnionFind(n)

for _ in range(k):
    p, q = map(int, input().split())
    uf.unite(q-1, p-1)
for _ in range(l):
    r, s = map(int, input().split())
    uf2.unite(s-1, r-1)

table = [[0]*n for _ in range(n)]
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    table[i][j] += 1
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    print(table[i][j], end=' ')


exit(0)
for i in range(n):
    ans = 0
    for j in range(n):
        if uf.same(i, j) and uf2.same(i, j):
            ans += 1
    print(ans, end=' ')

### FIXED CODE ###

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


class UnionFind():
    def __init__(self, n):
        self.tree = [i for i in range(n)]

    def root(self, x):
        if(self.tree[x] == x):
            return x
        self.tree[x] = self.root(self.tree[x])
        return self.tree[x]  # 経路圧縮

    def same(self, x, y):  # xとyが同じ木に属するか
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if(x == y):
            return
        self.tree[x] = y


uf = UnionFind(n)
uf2 = UnionFind(n)

for _ in range(k):
    p, q = map(int, input().split())
    uf.unite(q-1, p-1)
for _ in range(l):
    r, s = map(int, input().split())
    uf2.unite(s-1, r-1)

#table = [[0]*n for _ in range(n)]
table = dict()

for i in range(n):
    #table[uf.root(i)][uf2.root(i)] += 1
    table[(uf.root(i), uf2.root(i))] = table.get(
        (uf.root(i), uf2.root(i)), 0)+1
for i in range(n):
    print(table[(uf.root(i), uf2.root(i))], end=' ')

exit(0)
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    table[i][j] += 1
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    print(table[i][j], end=' ')


exit(0)
for i in range(n):
    ans = 0
    for j in range(n):
        if uf.same(i, j) and uf2.same(i, j):
            ans += 1
    print(ans, end=' ')
### BUGGY CODE ###

N,M=map(int,input().split())
a=list(map(int,input().split()))
for m in range(M):
  max_=max(a)
  a.remove(max_)
  a.append(max_//2)
print(sum(a))

### FIXED CODE ###

from heapq import heapify,heappush,heappop

N,M = map(int,input().split())
a = list(map(int,input().split()))
a = [(-x, x) for x in a]

heapify(a)

for m in range(M):
  max_ = heappop(a)
  a_ = max_[1]//2
  heappush(a,(-a_,a_))

ans=0
for a_ in a:
  ans+=a_[1]
print(ans)
### BUGGY CODE ###

while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	T = [[0]*1261 for i in range(M)]
	r = input()
	tnms = sorted([map(int,raw_input().split()) for i in range(r)], key = lambda x:x[1])
	for i in range(0,r,2):
		t1,n,m,s = tnms[i]
		t2,n,m,s = tnms[i+1]
		T[m-1][t1:t2] = [1 for j in range(t1,t2)]
	for m in range(M):
		c = 0
		for i in range(1260):
			if T[m-1][i]:
				c += 1
			T[m-1][i] = c - T[m-1][i+1]
	for i in range(input()):
		ts,te,m = map(int,raw_input().split())
		print T[m-1][te] - T[m-1][ts]

### FIXED CODE ###

while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	T = [[0]*1261 for i in range(M)]
	r = input()
	tnms = sorted([map(int,raw_input().split()) for i in range(r)], key = lambda x:x[1])
	for i in range(0,r,2):
		t1,n,m,s = tnms[i]
		t2,n,m,s = tnms[i+1]
		T[m-1][t1:t2] = [1 for j in range(t1,t2)]
	for i in range(input()):
		ts,te,m = map(int,raw_input().split())
		print sum(T[m-1][ts:te])
### BUGGY CODE ###

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, math.ceil(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True


# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if is_prime(i):
        primetable[i] = 1
# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2] == 1:
        like2017table[i] = 1


n = int(input())
queries = []
for _ in range(n):
    queries.append(list(map(int, input().split())))

for query in queries:
    begin = query[0]
    end = query[1]
    ans = sum(like2017table[begin:end+1])
    print(ans)


### FIXED CODE ###

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, math.ceil(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True


# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if is_prime(i):
        primetable[i] = 1

# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2] == 1:
        like2017table[i] = 1

# 累積和を計算する
cumsum = [ 0 for i in range(100001) ]
currentSum = 0
for i in range(2, 100001):
    currentSum += like2017table[i]
    cumsum[i] = currentSum

n = int(input())
queries = []
for _ in range(n):
    queries.append(list(map(int, input().split())))

for query in queries:
    begin = query[0]
    end = query[1]
    ans = cumsum[end] - cumsum[begin-1]
    print(ans)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        v = 4 * h * n - N * n - N * h
        if v == 0:
            continue
        w = (N * h * n) / v
        if w.is_integer() and w > 0:
            print(h, n, int(w))
            quit()

### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        v = 4 * h * n - N * n - N * h
        if v == 0:
            continue
        w = (N * h * n) / v
        if w.is_integer() and w > 0:
            print(h, n, int(w))
            quit()
### BUGGY CODE ###

N = int(input())
HN = list(map(int, input().split(" ")))

Max = 0

for i in range(N - 1):
    Count = 0
    NowHeight = HN[i]
    for j in range(i+1, N):
        NextHeight = HN[j]
        if NowHeight >= NextHeight:
            NowHeight = NextHeight
            Count = Count + 1
        else:
            break
    if Count > Max:
        Max = Count

print(Max)

### FIXED CODE ###

N = int(input())
HN = list(map(int, input().split(" ")))
 
Max = 0
 
i = 0
while i < (N - 1):
    Count = 0
    NowHeight = HN[i]
    for j in range(i+1, N):
        NextHeight = HN[j]
        if NowHeight >= NextHeight:
            NowHeight = NextHeight
            Count = Count + 1
        else:
            break
    if Count > Max:
        Max = Count
    i = i + 1 + Count
 
print(Max)