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

from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.linalg import spsolve
import numpy as np

N = int(input())
A = np.array(input().split(), dtype=int)

mat = lil_matrix((N, N))
for i in range(N):
    j = (i + 1) % N
    mat[i, i] = 1
    mat[i, j] = 1
mat = csr_matrix(mat)

ans = (spsolve(mat, A) * 2).astype(int)
print(*ans)


### FIXED CODE ###

from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))
### BUGGY CODE ###

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

min_count = 10 ** 4 + 1

def dfs(h, w, before_black, count):
    if maze[h][w] == "#":
        is_black = True
        if not before_black:
            count += 1
    else:
        is_black = False
    if h == H-1 and w == W-1:
        global min_count
        if count < min_count:
            min_count = count
    elif h == H-1:
        dfs(h, w+1, is_black, count)
    elif w == W-1:
        dfs(h+1, w, is_black, count)
    else:
        dfs(h+1, w, is_black, count)
        dfs(h, w+1, is_black, count)

dfs(0,0,False,0)

print(min_count)


### FIXED CODE ###

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
done = [[10**4 + 1]*(W) for _ in range(H)]

min_count = 10 ** 4 + 1

def dfs(h, w, before_black, count):
    if maze[h][w] == "#":
        is_black = True
        if not before_black:
            count += 1
    else:
        is_black = False
    if done[h][w] <= count:
        return
    done[h][w] = count
    if h == H-1 and w == W-1:
        global min_count
        if count < min_count:
            min_count = count
    elif h == H-1:
        dfs(h, w+1, is_black, count)
    elif w == W-1:
        dfs(h+1, w, is_black, count)
    else:
        dfs(h+1, w, is_black, count)
        dfs(h, w+1, is_black, count)

dfs(0,0,False,0)
print(min_count)
### BUGGY CODE ###

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

def getSum(s, e):
    sum = 0
    for i in range(s, e):
        sum = sum + list[i]
    return sum

prev = 0
for i in range(0,n-1):
    diff = abs(getSum(0, i+1) - getSum(i+1, n))
    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)


### FIXED CODE ###

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

left= array[0]
right = sum(array) - left

prev = 0
for i in range(0,n-1):
    diff = abs(left - right)
    left = left + array[i+1]
    right = right - array[i+1]

    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)
### BUGGY CODE ###

import sys
H,W,M=map(int, input().split())
h=[]
w=[]
Hcount=[0 for _ in range(H)]
Wcount=[0 for _ in range(W)]
B=[]

for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    B.append((hi,wi))
    Hcount[hi-1]+=1
    Wcount[wi-1]+=1
h_max=[i for i, v in enumerate(Hcount) if v == max(Hcount)]
w_max=[i for i, v in enumerate(Wcount) if v == max(Wcount)]
#print(h_max,w_max)
for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        if (h_max[ii]+1,w_max[jj]+1) not in B:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)

### FIXED CODE ###

import sys
 
input = sys.stdin.readline
 
 
def main():
    H, W, M = map(int, input().split())
    row = [0] * (H)
    col = [0] * (W)
    bomb = set()
    for _ in range(M):
        h, w = map(int, input().split())
        bomb.add((h, w))
        row[h-1] += 1
        col[w-1] += 1
    row_max = max(row)
    row_index_list = [i for i, v in enumerate(row) if v == row_max]
    col_max = max(col)
    col_index_list = [i for i, v in enumerate(col) if v == col_max]
    ans = row_max + col_max - 1
    c = False
    for x in row_index_list:
        for y in col_index_list:
            if not (x + 1, y + 1) in bomb:
                c = True
                break
        if c:
            break
    if c:
        ans += 1
    print(ans)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [(0, min(S, MAX), 0)]
    ans = [None] * N
    remain = N
    while len(q) and remain:
        time, coin, cur = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
            remain -= 1
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, (time + D[cur], min(coin + C[cur], MAX), cur))
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if dcost <= coin:
                heappush(q, (time + dtime, coin - dcost, nxt))
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [[0, min(S, MAX), 0, -1]]
    ans = [None] * N
    remain = N
    while len(q) and remain:
        time, coin, cur, prev = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
            remain -= 1
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, [time + D[cur], min(coin + C[cur], MAX), cur, cur])
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if nxt != prev and dcost <= coin:
                heappush(q, [time + dtime, coin - dcost, nxt, cur])
    for i in range(1, N):
        print(ans[i])


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

import numpy as np

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

D = np.zeros(2*(10**5)+1,dtype=int)


for i in L:
    D[i] += 1

Dcopy = D

D = np.where(D>1,(D-1)*D/2,0)
temp = int(D.sum())

for j in range(len(L)):
    if Dcopy[L[j]] > 1:
        print(temp - Dcopy[L[j]] + 1)
    else:
        print(temp)

### FIXED CODE ###

import numpy as np

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

D = np.zeros(2*(10**5)+1,dtype=int)


for i in L:
    D[i] += 1

Dcopy = D

# D = np.where(D>1,(D-1)*D/2,0)
D = D*(D-1)/2
temp = int(D.sum())

for j in range(len(L)):
    if Dcopy[L[j]] > 1:
        print(temp - Dcopy[L[j]] + 1)
    else:
        print(temp)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
k = 0
while True:
    l, r = map(int, input().split())
    print(s[l-1:r].count('AC'))
    k += 1
    if q <= k:
        break


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
k = 0
sum_c = [0 for _ in range(n)]
cnt = 0
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cnt += 1
    sum_c[i+1] = cnt

while True:
    l, r = map(int, input().split())
    print(sum_c[r-1]-sum_c[l-1])
    k += 1
    if q <= k:
        break
### BUGGY CODE ###

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


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans))


### FIXED CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))
### BUGGY CODE ###

# coding: utf-8
import sys
import itertools
sys.setrecursionlimit(1000000)
n=int(input())
a=list(map(int,input().split()))
d=[0]+list(itertools.accumulate(a))
memo={}
ans=0
def split_slime(l,r):
    global ans
    if (l,r) in memo:
        return memo[(l,r)]
    if l+1==r:
        return 0
    mn=10**18
    m=0
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
            m=i
    memo[(l,r)]=mn
    return memo[(l,r)]
print(split_slime(0,n))

### FIXED CODE ###

# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo=[[-1 for i in range(401)]for i in range(401)]
def split_slime(l,r):
    if l+1==r:
        return 0
    if memo[l][r]!=-1:
        return memo[l][r]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[l][r]=mn
    return memo[l][r]
print(split_slime(0,n))
### BUGGY CODE ###

import math
n = int(input())
s = input()
r_cnt = 0
g_cnt = 0
b_cnt = 0
for i in s:
    if i == 'R':
        r_cnt += 1
    elif i == 'G':
        g_cnt += 1
    elif i == 'B':
        b_cnt += 1
        
total = r_cnt*g_cnt*b_cnt

if n < 4:
    print(0)

else:
    for i in range(1,math.floor(len(s)-3/2)):
        for j in range(n-2*i):
            tmp = s[j]+s[j+i]+s[j+2*i]
            if (tmp == 'RGB') or (tmp == 'RBG') or (tmp == 'GBR') or (tmp == 'GRB') or (tmp == 'BRG') or (tmp == 'BGR'):
                total -= 1

    print(total)


### FIXED CODE ###

import math
n = int(input())
s = input()
r_cnt = 0
g_cnt = 0
b_cnt = 0
for i in s:
    if i == 'R':
        r_cnt += 1
    elif i == 'G':
        g_cnt += 1
    elif i == 'B':
        b_cnt += 1
        
total = r_cnt*g_cnt*b_cnt

if n < 4:
    print(0)

else:
    for i in range(1,math.floor((len(s)-2)/2)+10):
        for j in range(n-2*i):
            tmp = s[j]+s[j+i]+s[j+2*i]
            if (tmp == 'RGB') or (tmp == 'RBG') or (tmp == 'GBR') or (tmp == 'GRB') or (tmp == 'BRG') or (tmp == 'BGR'):
                total -= 1

    print(total)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

MOD = 2  # type: int


def solve(N: int, a: "List[int]"):
    a = np.array(a)
    ans = np.zeros(N)
    # print(ans)
    ans_idx = []
    for i in range(N - 1, -1, -1):
        # print(i)
        # print(list(range(i * 2 + 1, N, i + 1)))
        # print(ans[range(i * 2 + 1, N, i + 1)])
        # print()
        if (a[i] + ans[list(range(i * 2 + 1, N, i + 1))].sum()) % 2 == 0:
            ans[i] = 0
        else:
            ans[i] = 1
            ans_idx.append(i + 1)
    # print(ans)
    b = int(sum(ans))
    print(b)
    if b:
        print(*ans_idx)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 2  # type: int


def solve(N: int, a: "List[int]"):
    ans = [0 for x in range(N)]
    for i in range(N - 1, -1, -1):
        s = 0
        for j in range(i, N, i + 1):
            s += ans[j]
        # print(s, a[i], s ^ a[i])
        if (s + a[i]) & 1:
            ans[i] = 1
    # print(ans)
    b = int(sum(ans))
    print(b)
    l = []
    if b:
        for i, x in enumerate(ans):
            if x == 1:
                l.append(i + 1)
        print(*l)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

import itertools

n = int(input())

tl = [i for i in range(1, n+1) if i % 10 != 0]

l = list(itertools.product(tl, tl))

# print(l)

ans = []
count = 0
for pair in l:
    a = str(pair[0])
    b = str(pair[1])
    if (a[0] == b[len(b)-1]) and (a[len(a)-1] == b[0]):
        count += 1
        # ans.append(pair)

print(count)
# print(ans)


### FIXED CODE ###

import itertools

n = int(input())

tl = [i for i in range(1, n+1) if i % 10 != 0]

"""
l = list(itertools.product(tl, tl))

# print(l)

ans = []
count = 0
for pair in l:
    a = str(pair[0])
    b = str(pair[1])
    if (a[0] == b[len(b)-1]) and (a[len(a)-1] == b[0]):
        count += 1
        # ans.append(pair)

print(count)
# print(ans)
"""

c = [[0 for j in range(10)] for i in range(10)]
for k in range(1, n+1):
    i = int(str(k)[0])  # 先頭 k=114514 なら1
    j = int(str(k)[len(str(k))-1])  # 末尾 k=114514 なら4
    c[i][j] += 1

count = 0
# print(c)
for i in range(10):
    for j in range(10):
        count += c[i][j]*c[j][i]

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

#E問題
import bisect

N = int(input())
A = [int(input()) for i in range(N)]
B = [0]
for i in range(N):
    if i == 0:
        B[0]=A[i]
    else:
        if B[0] >= A[i]:
            B.insert(0,A[i])
        else:
            index = bisect.bisect_left(B,A[i])-1
            B[index] = A[i]
b=len(B)
print(b)

### FIXED CODE ###

#E問題
import heapq
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
A = A[::-1]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        li = bisect.bisect_right(C,A[i])
        if li == len(C):
            C.append(A[i])
        else:
            C[li] = A[i]
    
print(len(C))
### BUGGY CODE ###

import sys

_ = input()
a = map(int, input().split())
cnt = 0
 
while(1):
  flg = 0
  for i in a:
    if(i%2 == 1):
      flg = 1
      print(cnt)
      sys.exit()
      
  if(flg == 0):
    a = map(lambda x:x/2, a)
    cnt += 1
  else:
    break
 


### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
### BUGGY CODE ###

N = int(input())
A =[]
for _ in range(N):
  A.append(int(input()))
for i in range(N):
  ta = A[:]
  ta.pop(i)
  print(max(ta))

### FIXED CODE ###

N = int(input())
A =[]
for _ in range(N):
  A.append(int(input()))
a = max(A)
a2= max(sorted(A)[:-1])
f = False
if(a == a2):
  f = True
for i in range(N):
  if(f):
    print(a)
  elif(A[i] == a):
    print(a2)
  else:
    print(a)
### BUGGY CODE ###

n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    ww,vv=map(int,input().split())
    weight.append(ww)
    value.append(vv)
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(0,n):
    for w_sum in range(w+1):
        if w_sum >= weight[i]:
            dp[i+1][w_sum]=max(dp[i+1][w_sum],dp[i][w_sum-weight[i]]+value[i])
        dp[i+1][w_sum]=max(dp[i+1][w_sum],dp[i][w_sum])
print(dp[n][w])


### FIXED CODE ###

n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    ww,vv=map(int,input().split())
    weight.append(ww)
    value.append(vv)
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(0,n):
    for w_sum in range(w+1):
        if w_sum >= weight[i]:
            dp[i+1][w_sum]=max(dp[i+1][w_sum],dp[i][w_sum-weight[i]]+value[i])
        dp[i+1][w_sum]=max(dp[i+1][w_sum],dp[i][w_sum])
print(dp[n][w])
### BUGGY CODE ###

n = int(input())
ls = list(map(int,input().split()))
a = min(ls)
b = max(ls)
c = len(ls)
s = 0
def sub(p,q):
    return p-q
ans = []
aaa = [0]*(b+1)
for i in range(a,b+1):
    new = [i]*(c)
    ans = map(sub,ls,new)
    ans = list(map(str,ans))
    s = ans.count("-1") + ans.count("1") + ans.count("0")
    aaa[i] = s
print(max(aaa))

### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
di = [0]*(max(ls)+3)
for i in ls:
    di[i] += 1
    di[i+1] += 1
    di[i+2] += 1
print(max(di))
### BUGGY CODE ###

from operator import itemgetter
import bisect
import numpy as np

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

trains = [list(map(int, input().split())) for _ in range(M)]
trains = np.array(sorted(trains, key=itemgetter(0)))
query = [map(int, input().split()) for _ in range(Q)]
bleft = bisect.bisect_left
bright = bisect.bisect_right
ans = []
for p, q in query:
    li = bleft(trains[:, 0].ravel(), p)
    # print(trains[:li])
    tmpTrains = sorted(trains[li:, 1].ravel())
    ri = bright(tmpTrains, q)
    ans.append(ri)
print("\n".join(map(str, ans)))


### FIXED CODE ###

N, M, Q = map(int, input().split())
X = [[0 for _ in range(N)] for _ in range(N)]


for _ in range(M):
    l, r = list(map(int, input().split()))
    X[l-1][r-1] += 1
C = []
for line in X:
    tmp = [0, ]
    for c in line:
        tmp.append(tmp[-1] + c)
    C.append(tmp)
query = [map(int, input().split()) for _ in range(Q)]
# print(X)
# print(C)

for p, q in query:
    ans = 0
    for i, line in enumerate(C):
        if p-1 <= i and i <= q-1:
            ans += line[q] - line[p-1]
    print(ans)
### BUGGY CODE ###

h,w,d=map(int,input().split())
a=[]
l=[[] for i in range(h*w+1)]
for i in range(h):
    p=[int(j) for j in input().split()]
    a.append(p)
    for j in range(w):
        l[int(p[j])].append(i)
        l[int(p[j])].append(j)

q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    ans=0
    p=(lr[1]-lr[0])//d
    for j in range(p):
        ans+=abs(l[lr[0]+d*j][0]-l[lr[0]+d*(j+1)][0])+abs(l[lr[0]+d*j][1]-l[lr[0]+d*(j+1)][1])
    print(ans)




### FIXED CODE ###

h,w,d=map(int,input().split())
a=[]
l=[[] for i in range(h*w+1)]
for i in range(h):
    p=[int(j) for j in input().split()]
    a.append(p)
    for j in range(w):
        l[int(p[j])].append(i)
        l[int(p[j])].append(j)
cost=[0 for i in range(h*w+1)]
for i in range(1,h*w+1-d):
    cost[i+d]=cost[i]+abs(l[i+d][0]-l[i][0])+abs(l[i][1]-l[i+d][1])
q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    print(cost[lr[1]]-cost[lr[0]])
### BUGGY CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline


def lcm(a, b):
    return a * b // gcd(a, b)


mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
prev = A[0]
for a in A:
    l = lcm(prev, a)
    factor = l // prev
    ans = (ans * factor + l // a) % mod
    prev = l
print(ans)


### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline


def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)

    
def lcm(a, b):
    return a * b // gcd(a, b)


mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
inv_sum = 0
l = A[0]
for a in A:
    l = lcm(l, a)
    inv_sum = (inv_sum + mod_inverse(a)) % mod
print(l * inv_sum % mod)
### BUGGY CODE ###

import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

Q = int(input())

a = [0]*10**5
ans = []

for i in range(Q):
    l,r = map(int,input().split())
    prime = isPrime_np(r)
    pset = set(prime)
    for p in prime:
        if (p+1)/2 in pset:
            a[p] = 1
    ans.append(sum(a[l:r+1]))

print(*ans,sep="\n")

### FIXED CODE ###

import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
for i in range(MaxQ-1):
    s[i+1] = s[i] + a[i]
    
for l,r in lr:
    ans.append(s[r+1] - s[l])
print(*ans,sep="\n")
### BUGGY CODE ###

import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = []
  a = int(s)
  r.append(a%p)
  for i in range(n):
    a = a-int(s[i])*10**(n-1-i)
    r.append(a%p)
  #print(r)
  r.sort()
  ans = 0
  cnt=1
  for i in range(len(r)-1):
    if r[i]==r[i+1]:
      cnt+=1
    else:
      ans +=cnt*(cnt-1)//2
      cnt=1
  print(ans+cnt*(cnt-1)//2)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

### FIXED CODE ###

from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a =[]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])%p*pow(10,i,p))%p)
  a = [0]+a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)
### BUGGY CODE ###

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

ans = [0] * n

for i in range(n-k+1):
  for j in range(k):
    ans[i] += (1 + p[i+j]) / 2

print(max(ans))

### FIXED CODE ###

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

ans = [0] * n

for j in range(k):
  ans[0] += (1 + p[j]) / 2
for i in range(1,n-k+1):
  ans[i] = ans[i-1] - (1 + p[i-1]) / 2 + (1 + p[i+k-1]) / 2

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

N,K=map(int,input().split())
H=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+5)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if (i-j)<0:
      continue
    dp[i]=min(dp[i-j]+abs(H[i-j]-H[i]),dp[i])
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])