백준-7562

from collections import deque

d = [[-2, 1], [-2, -1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]]


def move(board, cur_x, cur_y, dest_x, dest_y):
    q = deque()
    q.append((cur_x, cur_y))

    while q:
        x, y = q.popleft()
        if x == dest_x and y == dest_y:
            print(board[x][y])
            break
        for i in range(8):
            dx = x + d[i][0]
            dy = y + d[i][1]
            if dx < 0 or dy < 0 or dx >= L or dy >= L:
                continue
            if dx >= 0 and dy >= 0 and board[dx][dy] == 0:
                q.append([dx, dy])
                board[dx][dy] = board[x][y] + 1


N = int(input())
for _ in range(N):
    L = int(input())
    cur_y, cur_x = map(int, input().split())
    dest_y, dest_x = map(int, input().split())
    board = [[0] * L for _ in range(L)]
    move(board, cur_y, cur_x, dest_y, dest_x)