나이트의 이동

체스판 위에 나이트 하나가 놓여 있다. 나이트는 한 번의 이동으로 L자 형태로 움직인다. 즉, 한 방향으로 두 칸 이동한 뒤 그와 수직인 방향으로 한 칸 이동한 위치로 갈 수 있다. 따라서 현재 칸을 기준으로 최대 8개의 칸으로 이동할 수 있다.

나이트가 이동하려는 목표 칸이 주어졌을 때, 그 칸까지 이동하는 데 필요한 최소 이동 횟수를 구하여라.

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어진다.

• 첫째 줄: 체스판 한 변의 길이 $l$ ($4 \le l \le 300$). 체스판의 크기는 $l \times l$이며, 각 칸은 $\{0, \dots, l-1\} \times \{0, \dots, l-1\}$의 좌표 쌍으로 나타낸다.
• 둘째 줄: 나이트가 현재 있는 칸의 좌표.
• 셋째 줄: 나이트가 이동하려는 목표 칸의 좌표.

각 테스트 케이스마다 나이트가 시작 칸에서 목표 칸까지 이동하는 데 필요한 최소 이동 횟수를 한 줄에 하나씩 출력한다.