메모이제이션과 너비우선탐색을 이용하여 완전탐색을 한 뒤 체스의 나이트의 현재 지점에서 목표 지점까지 가는 최소 이동 횟수를 구함
from collections import deque
dx, dy = [2, 1, -1, -2, -2, -1, 1, 2], [1, 2, 2, 1, -1, -2, -2, -1] # 델타검색, 한 지점을 기준으로 말이 갈 수 있는 좌표를 이용 할 것임
def bfs():
queue = deque() # 속도를 위해 덱 사용하여 큐 구현
queue.append([start_row, start_col])
while queue:
r, c = queue.popleft()
for i in range(8): # 현재 지점에서 갈수 있는 좌표 8군데를 뽑아 보고
dr, dc = r + dx[i], c + dy[i]
if 0 <= dr < n and 0 <= dc < n and memo[dr][dc] > memo[r][c] + 1: # 이 좌표가 행렬 범위 안에 있고 여태까지 메모에 기록 된 최단거리보다 더 단시간에 갈수 있으면
memo[dr][dc] = memo[r][c] + 1 # 메모에 새로운 기록을 하고
queue.append([dr, dc]) # 해당 좌표를 큐에 추가하여 순서가 되면 해당 좌표를 기준으로 검색함
for T in range(1, int(input())+1): # 문제에서 주어진 테스트 케이스 만큼 반복
n = int(input()) # 정사각형 모양 행렬의 한쪽 길이
memo = [[1000000 for _ in range(n)] for _ in range(n)] # 메모이제이션을 사용하기 위한 행렬을 생성
start_row, start_col = list(map(int, input().split())) # 시작 지점 좌표 정보
target_row, target_col = list(map(int, input().split())) # 도착 지점 좌표 정보
memo[start_row][start_row] = 0
bfs() # 메모이제이션을 사용한 BFS 탐색
print(memo[target_row][target_col])
