25461번 - NMABCD

정수 $N$, $M$, $A$, $B$, $C$, $D$가 주어진다. 다음을 구해보자.

• 격자판의 크기는 $N \times M$이다.
• 행과 열의 번호는 $1$부터 시작한다.
• 시작 위치는 $A$행, $B$열이다.
• 도착 위치는 $C$행, $D$열이다.
• 각 칸은 최대 한 번만 방문할 수 있다.
• 한 칸에서 다른 칸으로의 이동은 위, 아래, 오른쪽, 왼쪽으로 인접한 칸으로만 가능하다.
• 최대한 많은 칸을 방문해야 한다.

첫째 줄에 테스트 케이스의 개수 $Q$가 주어진다. 둘째 줄부터 $Q$개의 줄에 테스트 케이스의 정보가 주어진다. 테스트 케이스의 정보는 한 줄로 이루어져 있고, $N$, $M$, $A$, $B$, $C$, $D$가 공백으로 구분되어 있다.

각각의 테스트 케이스마다 방문할 수 있는 최대 칸의 수를 출력한다.

• $1 ≤ N , M ≤ 5\,000$
• $1 ≤ Q ≤ 1\,600$
• $2 ≤ N \cdot M ≤ 100\,000$
• $1 ≤ A, C ≤ N$
• $1 ≤ B, D ≤ M$
• $(A, B) ≠ (C, D)$