Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

cache = {}

def calc(x, y):
    if (x, y) in cache:
        return cache[(x, y)]
    p1 = pos[x]
    p2 = pos[y]
    r = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    cache[(x, y)] = r
    return r

def calclr(l, r):
    if (l, r) in cache:
        return cache[(l, r)]
    result = 0
    x = l
    while x < r:
        y = x + D
        result += calc(x, y)
        x += D
    cache[(l, r)] = result
    return result

for l, r in LR:
    print(calclr(l, r))


Fixed submission:
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

for l, r in LR:
    print(dt[r] - dt[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

def calc(x, y, cache={}):
    if (x, y) in cache:
        return cache[(x, y)]
    p1 = pos[x]
    p2 = pos[y]
    r = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    cache[(x, y)] = r
    return r

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        result += calc(x, y)
        x += D
    print(result)


Fixed submission:
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

for l, r in LR:
    print(dt[r] - dt[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        p1 = pos[x]
        p2 = pos[y]
        result += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x += D
    print(result)


Fixed submission:
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

for l, r in LR:
    print(dt[r] - dt[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

def find(A, x):
    for i, row in enumerate(A):
        if x in row:
            return row.index(x), i
    return -1, -1

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        p1 = find(A, x)
        p2 = find(A, y)
        result += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x += D
    print(result)


Fixed submission:
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

for l, r in LR:
    print(dt[r] - dt[l])