Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

dic = defaultdict(int)


def count_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            dic[i] += 1
            if i != n // i:
                dic[n//i] += 1


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

for a in A:
    count_divisors(a)

for key in sorted(dic.keys(), reverse=True):
    if dic[key] in [n, n-1]:
        print(key)
        break


Fixed submission:
import fractions

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

L_gcd = [0]*(n+1)
R_gcd = [0]*(n+1)

for i in range(n):
    L_gcd[i+1] = fractions.gcd(L_gcd[i], A[i])
    R_gcd[n-i-1] = fractions.gcd(R_gcd[n-i], A[n-i-1])

ans = [0]*n

for i in range(n):
    ans[i] = fractions.gcd(L_gcd[i], R_gcd[i+1])

print(max(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

dic = defaultdict(int)


def count_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            dic[i] += 1
            if i != n // i:
                dic[n//i] += 1


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

for a in A:
    count_divisors(a)

for key in sorted(dic.keys(), reverse=True):
    if dic[key] in [n, n-1]:
        print(key)
        break

Fixed submission:
import fractions

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

L_gcd = [0]*(n+1)
R_gcd = [0]*(n+1)

for i in range(n):
    L_gcd[i+1] = fractions.gcd(L_gcd[i], A[i])
    R_gcd[n-i-1] = fractions.gcd(R_gcd[n-i], A[n-i-1])

ans = [0]*n

for i in range(n):
    ans[i] = fractions.gcd(L_gcd[i], R_gcd[i+1])

print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
S = int(S, 2)

A = 0
for i in range(0, n, 2):
    A += 2**i

B = 0
for i in range(1, n, 2):
    B += 2**i

ans = min(bin(S^A).count('1'), bin(S^B).count('1'))
print(ans)

Fixed submission:
S = input()
n = len(S)
S = int(S, 2)

A = '0b'
B = '0b'
for i in range(n):
    if i % 2 == 0:
        A += '0'
        B += '1'
    else:
        A += '1'
        B += '0'

ans = min(bin(S ^ int(A, 0)).count('1'), bin(S ^ int(B, 0)).count('1'))
print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
S = input()

compress = []
now = '1'
count = 0
for s in S:
    if s != now:
        compress.append(count)
        now = s
        count = 1
    else:
        count += 1
compress.append(count)

length = len(compress)
candidate = sum(compress[:2*k+1])
ans = candidate
if length <= 2*k+1:
    print(ans)
    exit()

for i in range(0, length-2*k-1, 2):
    if 2+k+2+i < length:
        candidate += compress[2*k+1+i] + compress[2*k+2+i] - compress[i] - compress[i+1]
    else:
        candidate += compress[2*k+1+i] - compress[i] - compress[i+1]
    ans = max(ans, candidate)

print(ans)

Fixed submission:
n, k = map(int, input().split())
S = input()

compress = []
now = '1'
count = 0
for s in S:
    if s != now:
        compress.append(count)
        now = s
        count = 1
    else:
        count += 1
compress.append(count)

length = len(compress)
candidate = sum(compress[:2*k+1])
ans = candidate
if length <= 2*k+1:
    print(ans)
    exit()

for i in range(0, length-2*k-1, 2):
    if 2*k+2+i < length:
        candidate += compress[2*k+1+i] + compress[2*k+2+i] - compress[i] - compress[i+1]
    else:
        candidate += compress[2*k+1+i] - compress[i] - compress[i+1]
    ans = max(ans, candidate)

print(ans)
Buggy python submission (verdict: Runtime Error):
sum_div = 0
M = []
for i in range(5):
    num = int(input())
    sum_div += num // 10
    mod = num % 10
    if mod != 0:
        M.append(mod)

waiting = 10*(len(M)-1) + min(M)
total = sum_div*10 + waiting
print(total)


Fixed submission:
sum_div = 0
M = []
for i in range(5):
    num = int(input())
    sum_div += num // 10
    mod = num % 10
    if mod != 0:
        M.append(mod)

if M:
    waiting = 10*(len(M)-1) + min(M)
else:
    waiting = 0
total = sum_div*10 + waiting
print(total)
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

ans = []
for x in range(X):
    if x >= K:
        break
    for y in range(Y):
        if x + y >= K:
            break
        for z in range(Z):
            if x + y + z >= K:
                break

            value = A[x] + B[y] + C[z]
            ans.append(value)

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])


Fixed submission:
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

ans = []
for x in range(X):
    if x+1 > K:
        break
    for y in range(Y):
        if (x+1) * (y+1) > K:
            break
        for z in range(Z):
            if (x+1) * (y+1) * (z+1) > K:
                break

            value = A[x] + B[y] + C[z]
            ans.append(value)

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

n = int(input())
mod = 10**9 + 7
A, G, C, T = 'A', 'G', 'C', 'T'
count = 0


def seq(length, s3, s2, s1):
    if length == n:
        global count
        count += 1
        count %= mod
        return

    if [s2, s1] == [A, G]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    elif [s2, s1] == [A, C]:
        for x in [A, C, T]:
            seq(length+1, s2, s1, x)

    elif [s2, s1] == [G, A]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    elif [s3, s1] == [A, G]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    elif [s3, s2] == [A, G]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    else:
        for x in [A, C, G, T]:
            seq(length+1, s2, s1, x)


seq(0, T, T, T)
print(count)

Fixed submission:
from collections import defaultdict

n = int(input())
mod = 10**9 + 7
DP = [defaultdict(int) for _ in range(n+1)]
DP[0]['TTT'] = 1

for length in range(n):
    for seq, count in DP[length].items():

        if seq[1:] in ['AG', 'GA'] or seq[:2] == 'AG' or seq[0]+seq[2] == 'AG':
            for ns in 'AGT':
                new_seq = seq[1:] + ns
                DP[length+1][new_seq] += count
                DP[length + 1][new_seq] %= mod

        elif seq[1:] == 'AC':
            for ns in 'ACT':
                new_seq = seq[1:] + ns
                DP[length + 1][new_seq] += count
                DP[length + 1][new_seq] %= mod

        else:
            for ns in 'ACGT':
                new_seq = seq[1:] + ns
                DP[length + 1][new_seq] += count
                DP[length + 1][new_seq] %= mod

ans = sum(DP[n].values()) % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, num):
        self.parent = list(range(num))
        self.size = [1] * num

    def get_root(self, node):
        root = self.parent[node]
        if root == node:
            return root
        else:
            root = self.get_root(root)
            self.parent[node] = root
            return root

    def are_in_same_union(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        if root1 == root2:
            return True
        else:
            return False

    def combine(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        self.parent[root2] = root1
        self.size[root1] += self.size[root2]


n, m = map(int, input().split())
pairs = [list(map(int, input().split())) for _ in range(m)]
pairs = pairs[::-1]
answers = []
UF = UnionFind(n+1)
ans = n*(n-1)//2
answers.append(ans)

for land1, land2 in pairs:
    if UF.are_in_same_union(land1, land2):
        ans = ans
    else:
        root1, root2 = UF.get_root(land1), UF.get_root(land2)
        ans -= UF.size[root1] * UF.size[root2]
        UF.combine(land1, land2)
    answers.append(ans)

answers.pop()
answers = answers[::-1]

for x in answers:
    print(x)


Fixed submission:
import sys
sys.setrecursionlimit(10**6)


class UnionFind:
    def __init__(self, num):
        self.parent = list(range(num))
        self.size = [1] * num

    def get_root(self, node):
        root = self.parent[node]
        if root == node:
            return root
        else:
            root = self.get_root(root)
            self.parent[node] = root
            return root

    def are_in_same_union(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        if root1 == root2:
            return True
        else:
            return False

    def combine(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        self.parent[root2] = root1
        self.size[root1] += self.size[root2]


n, m = map(int, input().split())
pairs = [list(map(int, input().split())) for _ in range(m)]
pairs = pairs[::-1]
answers = []
UF = UnionFind(n+1)
ans = n*(n-1)//2
answers.append(ans)

for land1, land2 in pairs:
    if UF.are_in_same_union(land1, land2):
        ans = ans
    else:
        root1, root2 = UF.get_root(land1), UF.get_root(land2)
        ans -= UF.size[root1] * UF.size[root2]
        UF.combine(land1, land2)
    answers.append(ans)

answers.pop()
answers = answers[::-1]

for x in answers:
    print(x)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools


n, a, b, c = map(int, input().split())
L = [int(input())for _ in range(n)]
L_perm = list(itertools.permutations(L))
ans = 10**9
for l in L_perm:
    for i in range(1, n-1):
        A_tree = l[:i]
        synthesis_A = 10 * (i-1)
        fix_A = abs(a-sum(A_tree))
        for j in range(i+1, n):
            B_tree = l[i:j]
            synthesis_B = 10 * (j-i-1)
            fix_B = abs(b-sum(B_tree))
            for k in range(j+1, n+1):
                C_tree = l[j:k]
                synthesis_C = 10 * (k-j-1)
                fix_C = abs(c-sum(C_tree))

                total = fix_A + fix_B + fix_C + synthesis_A + synthesis_B + synthesis_C
                ans = min(ans, total)

print(ans)

Fixed submission:
import itertools


n, a, b, c = map(int, input().split())
L = [int(input())for _ in range(n)]
L_perm = list(itertools.permutations(L))
ans = 10**9
for l in L_perm:
    for i in range(1, n-1):
        A_tree = l[:i]
        synthesis_A = 10 * (i-1)
        fix_A = abs(a-sum(A_tree))
        for j in range(i+1, n):
            B_tree = l[i:j]
            synthesis_B = 10 * (j-i-1)
            fix_B = abs(b-sum(B_tree))
            for k in range(j+1, n+1):
                C_tree = l[j:k]
                synthesis_C = 10 * (k-j-1)
                fix_C = abs(c-sum(C_tree))

                total = fix_A + fix_B + fix_C + synthesis_A + synthesis_B + synthesis_C
                ans = min(ans, total)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
H = list(map(int, input().split()))

for i in range(k):
    H.append(0)

cost = [float('INF')]*(n+k)
cost[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        jump = cost[i] + abs(H[i+j]-H[i])
        if jump < cost[i+j]:
            cost[i+j] = jump

print(cost[n-1])

Fixed submission:
n, k = map(int, input().split())
H = list(map(int, input().split()))

for i in range(k):
    H.append(0)

cost = [float('INF')]*(n+k)
cost[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        jump = cost[i] + abs(H[i+j]-H[i])
        if jump < cost[i+j]:
            cost[i+j] = jump

print(cost[n-1])
Buggy python submission (verdict: Runtime Error):
import numpy as np

W = int(input())
n, k = map(int, input().split())
width = []
importance = []

for _ in range(n):
    w, imp = map(int, input().split())
    width.append(w)
    importance.append(imp)

DP = [[[[0]*(W+1)] for _ in range(n+1)] for _ in range(k+1)]

for i in range(1, n+1):
    for w in range(1, W+1):
        for k in range(0, k):
            wid = width[i-1]
            imp = importance[i-1]

            if w + wid <= W:
                DP[i][w+wid][k+1] = DP[i-1][w][k] + imp
            DP[i][w] = max(DP[i][w], DP[i-1][w])

ans = np.argmax(DP[n])
print(ans)


Fixed submission:
n, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]
DP = [[0]*2*W for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]
DP = [[0]*2*W for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)

Fixed submission:
n, W = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]
DP = [[0]*2*W for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input())
if a * b % 2 == 1:
    print('Yes')
else:
    print('No')

Fixed submission:
a, b = map(int, input().split())
if a * b % 2 == 1:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
X = list(map(int, input().split()))

count_0 = X.count(0)

if k <= count_0:
    print(0)
    exit()

k -= count_0

neg = [x for x in X if x < 0]
pos = [x for x in X if x > 0]

neg_count = len(neg)
pos_count = len(pos)

if not neg:
    print(pos[k-1])
    exit()

if not pos:
    print(neg[-k])
    exit()

res = []
for left in range(1, min(neg_count, k)):
    time1 = neg[-left]
    right = k - left - 1
    if right >= pos_count:
        continue
    elif right < 0:
        res.append(abs(time1))
    else:
        time2 = pos[right]
        res.append(time2-time1*2)

for right in range(min(pos_count, k)):
    time1 = pos[right]
    left = k - right - 1
    if left >= neg_count:
        continue
    elif left <= 0:
        res.append(abs(time1))
    else:
        time2 = neg[-left]
        res.append(time1*2-time2)

print(min(res))

Fixed submission:
n, k = map(int, input().split())
X = list(map(int, input().split()))

ans = []
for i in range(n-k+1):
    left = X[i]
    right = X[i+k-1]
    if left * right < 0:
        result = min(abs(left), abs(right)) * 2 + max(abs(left), abs(right))
    else:
        result = max(abs(left), abs(right))
    ans.append(result)

print(min(ans))

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
X = list(map(int, input().split()))

count_0 = X.count(0)

if k <= count_0:
    print(0)
    exit()

k -= count_0

neg = [x for x in X if x < 0]
pos = [x for x in X if x > 0]

neg_count = len(neg)
pos_count = len(pos)

if not neg:
    print(pos[k-1])
    exit()
if not pos:
  	print(neg[-k])
    exit()

res = []
for left in range(1, min(neg_count, k)):
    time1 = neg[-left]
    right = k - left - 1
    if right >= pos_count:
        continue
    elif right < 0:
        res.append(abs(time1))
    else:
        time2 = pos[right]
        res.append(time2-time1*2)

for right in range(min(pos_count, k)):
    time1 = pos[right]
    left = k - right - 1
    if left >= neg_count:
        continue
    elif left <= 0:
        res.append(abs(time1))
    else:
        time2 = neg[-left]
        res.append(time1*2-time2)


print(min(res))

Fixed submission:
n, k = map(int, input().split())
X = list(map(int, input().split()))

ans = []
for i in range(n-k+1):
    left = X[i]
    right = X[i+k-1]
    if left * right < 0:
        result = min(abs(left), abs(right)) * 2 + max(abs(left), abs(right))
    else:
        result = max(abs(left), abs(right))
    ans.append(result)

print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
start_ok = [set() for _ in range(n)]
end_ok = [set() for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    for x in range(start):
        start_ok[x].add(i)
    for y in range(end-1, n):
        end_ok[y].add(i)

for _ in range(q):
    left, right = map(int, input().split())
    possible = start_ok[left-1] & end_ok[right-1]
    print(len(possible))


Fixed submission:
import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
from collections import defaultdict
input = sys.stdin.readline


n, m, q = map(int, input().split())
train = defaultdict(list)
for _ in range(m):
    start, end = map(int, input().split())
    train[start].append(end)

for num in range(n):
    train[num].sort()

for _ in range(q):
    left, right = map(int, input().split())
    count = 0
    for num in range(left, right+1):
        candidate = train[num]
        possible = bisect.bisect_right(candidate, right)
        count += possible
    print(count)


Fixed submission:
import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

print(dic['C']%mod)


Fixed submission:
S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

    dic[''] %= mod
    dic['A'] %= mod
    dic['B'] %= mod
    dic['C'] %= mod

print(dic['C']%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, m = map(int, input().split())
DP = [[np.array([0, 0, 0]) for j in range(m+1)] for i in range(8)]

for _ in range(n):
    xyz = list(map(int, input().split()))
    for sign in range(8):
        check = np.zeros(3, dtype=np.int)
        for i in range(3):
            if (sign >> i) & 1:
                check[i] = 1
            else:
                check[i] = -1

        for i in range(m-1, -1, -1):
            candidate = DP[sign][i] + xyz
            delta = DP[sign][i+1] - DP[sign][i]
            delta_value = sum(delta*check)
            if delta_value < sum(xyz*check):
                DP[sign][i+1] = DP[sign][i] + xyz

ans = 0
for i in range(8):
    total = sum(np.abs(DP[i][m]))
    ans = max(ans, total)

print(ans)


Fixed submission:
n, m = map(int, input().split())
cakes = []
for i in range(n):
    x, y, z = map(int, input().split())
    cakes.append([x, y, z])

ans = []
for sign in range(8):
    check = [0, 0, 0]
    for i in range(3):
        if (sign >> i) & 1:
            check[i] = 1
        else:
            check[i] = -1

    cakes.sort(reverse=True, key=lambda x: x[0]*check[0] + x[1]*check[1] + x[2]*check[2])
    value = [0, 0, 0]
    for i in range(m):
        a, b, c = cakes[i]
        value[0] += a
        value[1] += b
        value[2] += c
        
    candidate = 0
    for i in range(3):
        candidate += abs(value[i])

    ans.append(candidate)

print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = input()
ans = n

for i in range(n):
    num = S[:i].count('W') + S[i+1:].count('E')
    if num < ans:
        ans = num
print(ans)


Fixed submission:
n = int(input())
S = input()
ans = n
num_list = []
W_count = 0

for i in range(n):
    if S[i] == 'W':
        W_count += 1
    num_list.append(W_count)

for i in range(1, n-1):
    left_w = num_list[i-1]
    right_e = n - num_list[n-1] - (1+i - num_list[i])
    pre_ans = left_w + right_e
    if ans > pre_ans:
        ans = pre_ans

ans_0 = n-num_list[n-1] - (1-num_list[0])
ans_n = num_list[n-2]
print(min(ans, ans_0, ans_n))
Buggy python submission (verdict: Runtime Error):
H, W, D = map(int, input().split())

dic = {}


def magic_test(L, R, power):
    if L == R:
        return power
    x, y = dic[L]
    nx, ny = dic[L+D]
    power += abs(x-nx) + abs(y-ny)
    return magic_test(L+D, R, power)


for y in range(1, H+1):
    A = list(map(int, input().split()))

    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = magic_test(L, R, 0)
    print(ans)


Fixed submission:
H, W, D = map(int, input().split())

dic = {}
K = H*W//D
memo = [[0]* (K+1) for _ in range(D+1)]

for y in range(1, H+1):
    A = list(map(int, input().split()))
    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

for extra in range(H*W+1, H*W+2*D):
    dic[extra] = [0, 0]

for i in range(1, D+1):
    for j in range(K):
        x, y = dic[i+D*j]
        nx, ny = dic[i+D*(j+1)]
        cost = abs(x-nx) + abs(y-ny)
        memo[i][j+1] = memo[i][j] + cost

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    j = L//D
    delta = (R-L)//D
    if i == 0:
        i = D
        j -= 1
    ans = memo[i][j+delta] - memo[i][j]
    print(ans)