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

import sys
sys.setrecursionlimit(1000000)

MOD = 10**9 + 7

def ex_euclid(a,b,c,d):
    if (b == 1) : return d
    x = a // b
    y = a % b
    return ex_euclid(b,y,d,(c[0]-x*d[0],c[1]-x*d[1]))
    
 
def mod_inv(a,p):
    x = ex_euclid(p,a,(1,0),(0,1))
    return x[1] % p

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

gp = b-a+1

dp = [[-1 for j in range(n+1)] for i in range(gp)]

tb1=[0,1]
tb2=[1] #便宜上0の逆元は0にする
for i in range(2,n+1):
    tb1.append((tb1[i-1]*i) % MOD)
for i in range(1,n+1):
    tb2.append(mod_inv(tb1[i],MOD))
    

for i in range(gp):dp[i][0] = 1


def dfs(sum,k):
    summ = sum
    if(k < 0):
        if (sum != 0):return 0
        else : return 1
    if dp[k][sum] != -1: return dp[k][sum]
    kk = k+a
    temp = dfs(sum,k-1)
    temp1 = 1
    for i in range(c-1):
        if (sum < 0):break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD 
        sum -= kk
    for i in range(c,d+1):
        if(sum-kk < 0) : break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD
        sum -= kk
        temp = (temp + temp1*dfs(sum,k-1)*tb2[i]) % MOD

    dp[k][summ] = temp
    return temp
    

        
ans = dfs(n,gp-1)



print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

MOD = 10**9 + 7

def ex_euclid(a,b,c,d):
    if (b == 1) : return d
    x = a // b
    y = a % b
    return ex_euclid(b,y,d,(c[0]-x*d[0],c[1]-x*d[1]))
    
 
def mod_inv(a,p):
    x = ex_euclid(p,a,(1,0),(0,1))
    return x[1] % p

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

gp = b-a+1

dp = [[-1 for j in range(n+1)] for i in range(gp)]

tb1=[0,1]
tb2=[1] #便宜上0の逆元は0にする
for i in range(2,n+1):
    tb1.append((tb1[i-1]*i) % MOD)
for i in range(1,n+1):
    tb2.append(mod_inv(tb1[i],MOD))
    

for i in range(gp):dp[i][0] = 1


def dfs(sum,k):
    summ = sum
    if(k < 0):
        if (sum != 0):return 0
        else : return 1
    if dp[k][sum] != -1: return dp[k][sum]
    kk = k+a
    temp = dfs(sum,k-1)
    temp1 = 1
    for i in range(c-1):
        if (sum < 0):break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD 
        sum -= kk
    for i in range(c,d+1):
        if(sum-kk < 0) : break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD
        sum -= kk
        temp = (temp + temp1*dfs(sum,k-1)*tb2[i]) % MOD

    dp[k][summ] = temp
    return temp
    

        
ans = dfs(n,gp-1)



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

K,S = map(int,input().split())
ans = 0
for i in range(0,K+1):
    for j in range(0,K+1):
        for k in range(0,K+1):
            if(i+j+k==S):
                ans += 1
            else:
                pass
print(ans)


### FIXED CODE ###

K, S = list(map(int, input().split()))
ans = 0
for i in range(K + 1):
    n = S - i
    if i <= S and n <= K * 2:
        a = (n + 1) - max(0, n - K) * 2
        ans += a
print(ans)
### BUGGY CODE ###

def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def _is_prime(n):
    for i in range(n - 1):
        if (i + 1) ** (n - 1) % n != 1:
            return False
    return True

a, b = map(int, input().split())
g = my_gcd(a, b)
count = 1
num = g
d = 2
while num > 1:
    if _is_prime(d):
        flag = True
        while not num % d:
            if flag:
                count += 1
                flag = False
            num = num // d
    d += 1
print(count)

### FIXED CODE ###

def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

a, b = map(int, input().split())
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s & t) + 1)
### BUGGY CODE ###

n, m, q = map(int, input().split())
trains = [list(map(int, input().split())) for _ in range(m)]
questions = [list(map(int, input().split())) for _ in range(q)]

for question in questions:
    x, y = question
    result = [train for train in trains if x <= train[0] and train[1] <= y]
    print(len(result))


### FIXED CODE ###

n, m, q = map(int, input().split())
cities = [[0 for _ in range(n+1)] for _ in range(n+2)]
trains = [list(map(int, input().split())) for _ in range(m)]
quests = [list(map(int, input().split())) for _ in range(q)]

for train in trains:
    x, y = train[0], train[1]
    cities[x][y] += 1

for i in range(n):
    for j in range(1, n-i+1):
        x = j + i
        cities[j][x] += cities[j][x-1] + cities[j+1][x] - cities[j+1][x-1]

for quest in quests:
    p, q = quest[0], quest[1]
    print(cities[p][q])
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 2**31
dp = [INF for i in range(N+1)]
dp[0],dp[1] = 0,0
dp[2] = abs(h[1]-h[0])
for i in range(3,N+1):
    dp[i] = min([dp[i-k]+abs(h[i-1]-h[i-1-k]) for k in range(1,min(i,K+1))])
print(dp[N])

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
h = [int(x) for x in input().split()]
h = np.array(h)
dp = np.zeros(N, dtype=int)
for i in range(1, N):
  j = max(0, i-K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(dp[N-1])
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
for i in range(1,n+1):
  p=k-q+1*(a.count(i))
  if p>=1:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[]
for i in range(n):
  a.append(k-q)
for i in range(q):
  a[int(input())-1]+=1
for i in range(n):
  print('Yes' if a[i]>0 else 'No')
### BUGGY CODE ###

from itertools import accumulate

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

cnt = 1
while cnt <= k and min(a) < n:
    li = [0] * (n + 1)
    for i, e in enumerate(a):
        l = max(0, i - e)
        r = min(n, i + e + 1)
        li[l] += 1
        li[r] -= 1

    a = list(accumulate(li))[:-1]

    cnt += 1

print(*a)


### FIXED CODE ###

from itertools import accumulate

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

cnt = 1
while cnt <= k and min(a) < n:
    li = [0] * (n + 1)
    for i, e in enumerate(a):
        l = max(0, i - e)
        r = min(n, i + e + 1)
        li[l] += 1
        li[r] -= 1

    a = list(accumulate(li))[:-1]

    cnt += 1

print(*a)
### BUGGY CODE ###

n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]
        if dp[miru-1] == n-1:
          flag = False
          break
        else:
          if B[miru-1] != 1:
            if L[miru-1][dp[miru-1]][1] == i+1:
              dp[i] += 1
              dp[miru-1] += 1
              B[miru-1] = 1
              act += 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  if cnt >= 350000:
      dp = [n-1]*n
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

### FIXED CODE ###

import time
start = time.time()
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
  ela = time.time()-start
  if ela > 1.7:
    dp = [n-1]*n
if flag == False:
  print(-1)
else:
  if ela < 1.7:
    print(cnt)
  else:
    print(n*(n-1)//2)
### BUGGY CODE ###

import copy

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

#print(S)
inf = 10 ** 3
data = [[[[inf for i in range(W+2)] for j in range(H+2)] for k in range(W+2)] for l in range(H+2)]

for i in range(1,H+1):
    for j in range(1,W+1):
        data[i][j][i][j] = 0

for m in range((H+2)*(W+2)//2):
    data_ = copy.copy(data)
    for i in range(1,H+1):
      for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if S[i][j] == "#" or S[k][l] == "#":
                    continue
                data_[i][j][k][l] = min(data[i][j][k][l],data[i][j][k+1][l]+1,data[i][j][k-1][l]+1,data[i][j][k][l+1]+1,data[i][j][k][l-1]+1)

x = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if x < data_[i][j][k][l] and data_[i][j][k][l] != inf:
                    x = data_[i][j][k][l]

print(x)


### FIXED CODE ###

#いい加減深さ優先探索, 幅優先探索をスムーズに実装してえなおい

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

inf = 10 ** 3
m = 0
mi = -1
mj = -1
mk = -1
ml = -1
  
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "#":
            continue
        data = [[inf]*(W+2) for k in range(H+2)]
        data[i][j] = 0
        stack = [[i,j,0]]
        while stack:
            x = stack.pop()
            if S[x[0]+1][x[1]] == "." and data[x[0]+1][x[1]]>x[2]+1:
                data[x[0]+1][x[1]] = x[2]+1
                stack.append([x[0]+1,x[1],x[2]+1])
            if S[x[0]][x[1]+1] == "." and data[x[0]][x[1]+1]>x[2]+1:
                data[x[0]][x[1]+1] = x[2]+1
                stack.append([x[0],x[1]+1,x[2]+1])
            if S[x[0]-1][x[1]] == "." and data[x[0]-1][x[1]]>x[2]+1:
                data[x[0]-1][x[1]] = x[2]+1
                stack.append([x[0]-1,x[1],x[2]+1])
            if S[x[0]][x[1]-1] == "." and data[x[0]][x[1]-1]>x[2]+1:
                data[x[0]][x[1]-1] = x[2]+1
                stack.append([x[0],x[1]-1,x[2]+1])
            #print(i,j,stack)

        for k in range(1,H+1):
            for l in range(1,W+1):
                if data[k][l] > m and data[k][l] != inf:
                    m = data[k][l]
                    mi = i
                    mj = j
                    mk = k
                    ml = l

#print(mi,mj,mk,ml)
print(m)

#DFSならワイの実装力でも割とスムーズにできそう？
#なんで昨日これやらなかったんや
#と言いつつWAするアホ
### BUGGY CODE ###

S = input()

len_S = len(S)

for i in range(len_S):
    S = S.replace("10", "")
    S = S.replace("01", "")

print(len_S - len(S))

### FIXED CODE ###

S = input()

count_one = S.count("1")
count_zero = S.count("0")

print(min(count_one, count_zero)*2)
### BUGGY CODE ###

N = int(input())
S = input()
# S = [s for s in S]
cnt = 0

# def my_index_multi(l, x):
#     return [i for i, _x in enumerate(l) if _x == x]
# R = my_index_multi(S, 'R')
# G = my_index_multi(S, 'G')
# B = my_index_multi(S, 'B')
R = []
G = []
B = []
for i, s in enumerate(S):
    if s=='R':
        R.append(i)
    elif s=='G':
        G.append(i)
    else:
        B.append(i)

for r in R:
    for g in G:
        for b in B:
            l = [r, g, b]
            l.sort()
            if (l[1]-l[0])!=(l[2]-l[1]):
                cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count('R')*S.count('G')*S.count('B')

for i in range(N):
    for j in range(i+1, N):
        if S[i]!=S[j]:
            k = 2*j-i
            if k < N and S[i]!=S[k] and S[j]!=S[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

from itertools import combinations

def get_t_strs(T):
  lenT = len(T)
  strs = ['?'*lenT, T]
  for i in range(1,lenT):
    cmbs = list(combinations([i for i in range(lenT)],i))
    for cmb in cmbs:
      T_list = [t for t in T]
      for idx in cmb: T_list[idx] = '?'
      strs.append(''.join(T_list))
  return strs

S,T = input(), input()
if S.count('?') == 0:
  print(S)
  exit()

idx_options = []
t_strs = get_t_strs(T)
for t_str in t_strs:
  idx = S.rfind(t_str)
  if idx != -1: idx_options.append(idx+1)

if len(idx_options) == 0: print('UNRESTORABLE')
else:
  max_idx = max(idx_options)
  print((S[:max_idx-1] + T + S[max_idx+len(T)-1:]).replace('?','a'))

### FIXED CODE ###

def is_matched(i, inputS, T):
  for s,t in zip(inputS, T):
    if s == '?': continue
    if s != t: return False
  return True

S, T = input(), input()
lenS, lenT = len(S), len(T)
matched_i = None
ans = []
for i in range(lenS-lenT+1):
  if is_matched(i, S[i:i+lenT], T):
    tmpS = S.replace('?', 'a')
    ans.append(''.join([s for s in S[:i].replace('?', 'a') + T + S[i+lenT:].replace('?', 'a')]))
if ans == []: print('UNRESTORABLE')
else: print(sorted(ans)[0])
### BUGGY CODE ###

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

d = {}
for i in range(n):
  if s[i] in d.keys():
    d[s[i]] += 1
  else:
    d[s[i]] = 1

m = max(d.values())
ans = []

for k, v in d.items():
  if v == m:
    ans.append(k)
ans.sort()
print(*ans, sep = "\n")

### FIXED CODE ###

from collections import Counter

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

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

k,s = map(int, input().split())
cnd = range(0, k+1)
print(str(sum([1 for x in cnd for y in cnd for z in cnd if x+y+z == s])))

### FIXED CODE ###

k,s = map(int, input().split())
cnd = range(0, k+1)
print(str(sum([1 for x in cnd for y in cnd if s-x-y in cnd])))
### BUGGY CODE ###

N = int(input())

P = list(map(int, input().split()))

cnt=0

import numpy as np

P=np.array(P)

cnt=0
for i in range(N):
    sub_list = P[:i]

    if len(sub_list)==0:
        cnt+=1
        continue

    max_P = np.min(np.sort(sub_list))

    if max_P >= P[i]:
        cnt+=1

print(cnt)

### FIXED CODE ###

N = int(input())

P = list(map(int, input().split()))

cnt=0

import numpy as np

P=np.array(P)

max_val=P[0]

cnt=1

for i in range(1,N):
    if max_val > P[i-1]:
        max_val=P[i-1]

    if max_val > P[i]:
        cnt+=1

print(cnt)
### BUGGY CODE ###

n=int(input())  #->n=5
ai=list(map(int,input().split()))  #->nl=[1,2,-,n]

temp = 0
for i in range(n-1):
    for j in range(i+1,n):
        temp = temp + ai[i]*ai[j]
        temp = temp % (10**9+7)

print(temp)



### FIXED CODE ###

#!/usr/bin/env python3

n=int(input())  #->n=5
a=list(map(int,input().split()))  #->nl=[1,2,-,n]
mod=int(1e9+7)

# Accumulate
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):  pre[i]=pre[i-1]+a[i]
ans=0
for i in range(1,n):  ans=(ans+(a[i-1]*(pre[n-1]-pre[i-1]))%mod)%mod
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
lst = np.asarray([0] * (n+1))
a = np.array(range(n+1))

for i in range(1,n+1):
    lst += (a % i == 0)

print(sum(lst*a))

### FIXED CODE ###

n = int(input())
cnt = 0
for i in range(1, n+1):
    hoge = n//i
    cnt += (hoge + 1) * i * hoge / 2
print(int(cnt))
### BUGGY CODE ###

h, n = map(int, input().split())
dp = [0] + [float('inf')] * h
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j + a, h)
        dp[nj] = min(dp[nj], dp[j] + b)
print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b in magics)
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print(dp[h])
### BUGGY CODE ###

dp,dp2,mod = [1]+[0]*12,[0]*13,10**9+7
for i in input():
    if i=="?":
        for k in range(10):
            for j in range(13): dp2[(j*10+k)%13] = (dp2[(j*10+k)%13]+dp[j])%mod
    else:
        for j in range(13): dp2[(j*10+int(i))%13] = (dp2[(j*10+int(i))%13]+dp[j])%mod
    dp,dp2 = dp2,[0]*13
print(dp[5])

### FIXED CODE ###

s = input()
ans,mod = [0]*13,10**9+7
if s[0]=="?": ans = [1]*10+[0]*3
else: ans[int(s[0])] = 1
for i in s[1:]:
    dp = [0]*13
    for j in range(13): dp[j*10%13] = ans[j]%mod
    dp+=dp
    if i=="?":
        for j in range(13): ans[j] = sum(dp[j+4:j+14])
    else:
        for j in range(13): ans[j] = dp[j+13-int(i)]
print(ans[5]%mod)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[0] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    while que:
        p = que.popleft()
        ans = d[p[0]][p[1]]
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == 0 and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
 
                #ans = max(ans, d[ny][nx])     
    return ans
print(bfs())


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]


def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                # A[ny][nx] = "#"
                que.append((ny, nx))
 
                ans = max(ans, d[ny][nx])     
#    print(*d, sep="\n")
    return ans


if __name__ == "__main__":
    print(bfs())
### BUGGY CODE ###

n, m = map(int, input().split())
c = [0]*n
for i in range(m):
  l, r = map(int, input().split())
  for j in range(l-1, r):
    c[j] += 1
print(c.count(m))

### FIXED CODE ###

n, m = map(int, input().split())
x, y = 1, n
for _ in range(m):
  a, b = map(int, input().split())
  x = max(a, x)
  y = min(b, y)
print(max(0, y-x+1))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)] 
 
A = sorted(A)
res = 0
A2 = []
for i in range(len(A)):
    if len(A) == 1:
        if abs(A[0] - A2[0]) < abs(A[0] - A2[-1]):
            A2.append(A[0])
        else:
            A2.insert(0,A[0])
        break
    if i % 2 == 0:
        if i == 0:
            A2.append(A.pop(-1))
        else:
            if abs(A[-1] - A2[0]) < abs(A[-1] - A2[-1]):
                A2.append(A.pop(-1))
            else:
                A2.insert(0,A.pop(-1))
    else:
        #A2.append(A.pop(0))
        if abs(A[0] - A2[0]) < abs(A[0] - A2[-1]):
            A2.append(A.pop(0))
        else:
            A2.insert(0,A.pop(0))
for i in range(len(A2)-1):
    res += abs(A2[i] - A2[i+1])

print(res)

### FIXED CODE ###

N = int(input())
A_in = [int(input()) for _ in range(N)] 
 
A = sorted(A_in)
res1 = 0
A2 = []
for i in range(len(A)):
    if len(A) == 1:
        if abs(A[0] - A2[0]) < abs(A[0] - A2[-1]):
            A2.append(A[0])
        else:
            A2.insert(0,A[0])
        break
    if i % 2 == 0:
        A2.append(A.pop(-1))
    else:
        A2.append(A.pop(0))
for i in range(len(A2)-1):
    res1 += abs(A2[i] - A2[i+1])

A = sorted(A_in,reverse=True)
res2 = 0
A2 = []
for i in range(len(A)):
    if len(A) == 1:
        if abs(A[0] - A2[0]) < abs(A[0] - A2[-1]):
            A2.append(A[0])
        else:
            A2.insert(0,A[0])
        break
    if i % 2 == 0:
        A2.append(A.pop(-1))
    else:
        A2.append(A.pop(0))
for i in range(len(A2)-1):
    res2 += abs(A2[i] - A2[i+1])

print(max(res1,res2))
### BUGGY CODE ###

def main():
    from collections import namedtuple
    from heapq import heappop, heappush
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Prog = namedtuple('Prog', 'L R ch')
    Prog.__eq__ = lambda self, other: self.R == other.R
    Prog.__lt__ = lambda self, other: self.R > other.R  # heapqで大きい方から出すため逆で定義

    N, C = map(int, input().split())
    ps = []
    for _ in range(N):
        p = Prog(*map(int, input().split()))
        ps.append(p)
    ps.sort(key=attrgetter('R'))

    rec = []
    for p in ps:
        tank = []
        while rec:
            if p.L < rec[0].R: continue
            recorder = heappop(rec)
            if (recorder.ch == p.ch and recorder.R <= p.L) or (recorder.R < p.L): break
            tank.append(recorder)
        for r in tank: heappush(rec, r)
        heappush(rec, p)
    print(len(rec))


if __name__ == '__main__':
    main()


### FIXED CODE ###

t_max = 10 ** 5

N, C = map(int, input().split())
imos = [[0] * (t_max + 1) for _ in range(C + 1)]
# imos[c][x]:=チャンネルc,時刻xの使用有無
# c: 1-indexed
# x: 1-indexed

for _ in range(N):
    s, t, c = map(int, input().split())
    imos[c][s] += 1
    imos[c][t] -= 1

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        imos[c][i] += imos[c][i - 1]
        if imos[c][i] > 0 and imos[c][i - 1] == 0:
            imos[c][i - 1] = imos[c][i]

ans = 0
for i in range(1, t_max + 1):
    ans = max(ans, sum(imos[c][i] for c in range(1, C + 1)))
print(ans)
### BUGGY CODE ###

finished = [False] * 10**5
isPN = [False] * 10**5
def isPrimeNumber(num):
  if finished[num]:
    return isPN[num]
  
  if num == 1:
    return False
  pn = 2
  while pn * pn <= num:
    if num % pn == 0:
      finished[num] = True
      isPN[num] = False
      return isPN[num]
    pn += 1
  
  
  finished[num] = True
  isPN[num] = True
  return isPN[num]

n = int(input())

l = [0] * n
r = [0] * n
for i in range(n):
  l[i], r[i] = map(int, input().split())
  
  
for i in range(n):
  ans = 0
  for j in range(l[i], r[i]+1, 2):
    if isPrimeNumber(j) and isPrimeNumber(int((j+1)/2)):
      ans += 1
      
  print(ans)

### FIXED CODE ###

max_num = 10**5+5
eratos_thenes_sieve = [0,0] + [1]*max_num
n = 2 #素数
while n*n <= max_num:
  if eratos_thenes_sieve[n]:#
    for i in range(2*n, max_num, n):
      eratos_thenes_sieve[i] = 0
  n += 1
  
isLike2017 = [0] * max_num
cumulativeSums = [0]
for i in range(max_num):
  if eratos_thenes_sieve[i] and eratos_thenes_sieve[(i+1)//2]:
    isLike2017[i] = 1
  cumulativeSums.append(cumulativeSums[-1] + isLike2017[i])
  
  
q = int(input())

for i in range(q):
  l, r = map(int, input().split())
  print(cumulativeSums[r+1] - cumulativeSums[l])