화가들의 대결

새로운 미술관이 곧 문을 엽니다. 이 건물은 단층이며, 큰 정삼각형 모양입니다. 건물은 같은 모양의 작은 정삼각형 방들로 이루어져 있고, 미술관의 한 변 길이는 방 한 변 길이의 $S$배입니다. 각 방에는 변을 공유하는 다른 방과 연결되는 문이 있습니다(꼭짓점만 공유하는 방은 해당하지 않습니다).

각 방은 두 수로 식별합니다. 첫 번째 수는 방이 있는 행(위에서 아래로, 1부터 셉니다)이고, 두 번째 수는 그 행에서의 위치(왼쪽에서 오른쪽으로, 1부터 셉니다)입니다. $S=3$일 때 방의 연결과 번호 체계는 다음과 같습니다.

앨마와 베르트는 미술관의 방을 칠하는 화가입니다. 앨마는 $(R_A, P_A)$ 방에서 시작하고, 베르트는 다른 방 $(R_B, P_B)$에서 시작합니다. 두 사람은 시작한 방을 이미 칠했습니다. 나머지 방 중 $C$개는 공사 중이며, 앨마와 베르트 모두 이 방에 들어가거나 칠할 수 없습니다.

앨마와 베르트는 차례대로 움직이는 게임을 하며, 앨마가 먼저 시작합니다. 자기 차례가 되면, 현재 방과 인접한 방 중 아직 칠하지 않았고 공사 중이 아닌 방이 하나라도 있으면 그중 하나를 골라 이동하고 그 방을 칠해야 합니다. 그렇지 않으면 이동하지 않고 그 차례에는 아무것도 하지 않습니다. 두 화가 모두 더 이상 움직일 수 없으면 게임이 끝납니다. 점수는 앨마가 칠한 방의 수에서 베르트가 칠한 방의 수를 뺀 값입니다.

두 화가는 최선의 선택을 합니다. 앨마는 점수를 최대화하려 하고, 베르트는 점수를 최소화하려 합니다. 베르트가 어떻게 행동하든 앨마가 보장할 수 있는 최고 점수를 구하세요.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 정수 여섯 개 $S$, $R_A$, $P_A$, $R_B$, $P_B$, $C$가 한 줄에 주어집니다. 차례대로 미술관의 한 변 길이(방 한 변 길이의 배수), 앨마 시작 방의 행과 위치, 베르트 시작 방의 행과 위치, 공사 중인 방의 수입니다. 그 뒤에 $C$개의 줄이 이어집니다. $i$번째 줄에는 $i$번째 공사 중인 방의 행 $R_i$와 위치 $P_i$가 주어집니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 앨마가 보장할 수 있는 최고 점수입니다.

• $0 \le C \le S^2 - 2$.
• $1 \le R_A \le S$.
• $1 \le P_A \le 2R_A - 1$.
• $1 \le R_B \le S$.
• $1 \le P_B \le 2R_B - 1$.
• $(R_A, P_A) \ne (R_B, P_B)$.
• 모든 $i$에 대해 $1 \le R_i \le S$.
• 모든 $i$에 대해 $1 \le P_i \le 2R_i - 1$.
• 모든 $i$에 대해 $(R_i, P_i) \ne (R_A, P_A)$.
• 모든 $i$에 대해 $(R_i, P_i) \ne (R_B, P_B)$.
• 모든 $i < C$에 대해 $R_i < R_{i+1}$이거나, $R_i = R_{i+1}$이고 $P_i < P_{i+1}$입니다.

샘플 케이스 #1에서 차례는 다음과 같이 진행됩니다.

1. 앨마가 (2, 2) 방으로 이동합니다.
2. 베르트는 이동할 수 없습니다.
3. 앨마가 (2, 3) 방으로 이동합니다.
4. 베르트는 여전히 이동할 수 없습니다.
5. 앨마는 이동할 수 없습니다. 두 화가 모두 이동할 수 없으므로 게임이 끝납니다.

앨마는 3개의 방을, 베르트는 1개의 방을 칠했으므로 점수는 3 - 1 = 2입니다.

샘플 케이스 #2에서는 두 화가 모두 이동할 수 없습니다. 두 사람은 시작 방만 칠합니다.

다음의 추가 케이스는 테스트 셋 1에는 나올 수 없지만, 테스트 셋 2에는 나올 수 있습니다.

2
3 3 4 2 1 2
2 3
3 1
3 3 2 2 3 2
2 1
3 1

이 두 케이스의 올바른 출력은 다음과 같습니다.

Case #1: 0
Case #2: -1

케이스 #1에서 앨마는 (3, 5) 또는 (3, 3)으로 이동할 수 있습니다. 공사 중인 (2, 3)으로는 이동할 수 없습니다.

• 앨마가 (3, 5)로 이동하면 앨마는 더 이상 움직일 수 없고, 베르트가 방 두 개를 더 칠합니다. 점수는 2 - 3 = -1입니다.
• 앨마가 (3, 3)으로 이동하면, 베르트는 (3, 2)로 이동할 수 있습니다. 이 경우 두 화가 모두 더 이상 움직일 수 없으며, 점수는 2 - 2 = 0입니다. 또는 베르트는 (2, 2)로 이동할 수 있습니다. 이 경우 앨마는 (3, 2)로, 베르트는 (1, 1)로 이동하며, 점수는 3 - 3 = 0입니다.

앨마는 (3, 3)으로 이동하면 베르트가 어떻게 하든 점수 0을 보장할 수 있음을 알고 있습니다. 이는 (3, 5)로 이동했을 때의 -1보다 낫습니다. 따라서 앨마는 (3, 3)으로 이동합니다. 이 게임의 나머지가 정확히 어떻게 진행될지는 알 수 없지만, 앨마가 보장할 수 있는 최고 점수는 알 수 있습니다. 공사 중이 아닌 방 중 하나 이상은 끝까지 칠해지지 않을 수도 있습니다.

케이스 #2에서 앨마는 반드시 (3, 3)으로 이동해야 하며, 그다음 베르트는 (2, 2)보다 (3, 4)로 이동하는 것이 유리합니다.