화가들의 결투

새 미술관이 곧 문을 연다! 이 미술관은 커다란 정삼각형 모양의 단층 건물이다. 이 삼각형은 크기와 모양이 같은 더 작은 정삼각형 모양의 방들로 이루어져 있으며, 미술관의 한 변의 길이는 어느 방이든 그 방의 한 변 길이의 S배이다. 각 방에는 변 하나를 공유하는(정점만 공유하는 경우는 제외한다) 다른 모든 방으로 연결되는 문이 있다.

각 방은 두 수로 식별된다. 먼저 그 방이 있는 건물의 행(위에서 아래로 1부터 센다)이 오고, 이어서 그 행 안에서의 위치(왼쪽에서 오른쪽으로 1부터 센다)가 온다. S = 3일 때 방들이 어떻게 연결되고 표기되는지를 보여 주는 예시는 다음과 같다.

Alma와 Berthe는 미술관의 방들을 칠하는 화가이다. Alma는 방 ($R_{A}$, $P_{A}$)에서 시작하고, Berthe는 그와 다른 방 ($R_{B}$, $P_{B}$)에서 시작한다. 두 사람은 각각 자신의 시작 방을 이미 칠했다. 미술관의 다른 방 중 C개는 공사 중이며, Alma와 Berthe는 이 방들에 들어가거나 이 방들을 칠할 수 없다.

Alma와 Berthe는 친선 경쟁으로 턴제 게임을 하며, Alma가 먼저 시작한다. 화가의 차례에 현재 방과 인접한 방 중 아직 칠하지 않았고 공사 중이 아닌 방이 적어도 하나 있다면, 화가는 그중 하나를 골라 그 방으로 이동하고 칠해야 한다. 그렇지 않으면 화가는 이동할 수 없으며 자신의 차례에 아무것도 하지 않는다. 두 화가 모두 이동할 수 없게 되면 게임이 끝난다. 게임의 점수는 Alma가 칠한 방의 수에서 Berthe가 칠한 방의 수를 뺀 값이다.

두 화가는 모두 최적의 결정을 내리며, Alma는 점수를 최대화하려 하고 Berthe는 점수를 최소화하려 한다. 이를 바탕으로 Berthe가 무엇을 하든 Alma가 게임에서 보장할 수 있는 최선의 점수를 구한다.

제한

시간 제한: 40초. 메모리 제한: 1 GB. 0 ≤ C ≤ $S^{2}$ - 2. 1 ≤ $R_{A}$ ≤ S. 1 ≤ $P_{A}$ ≤ 2 × $R_{A}$ - 1. 1 ≤ $R_{B}$ ≤ S. 1 ≤ $P_{B}$ ≤ 2 × $R_{B}$ - 1. ($R_{A}$, $P_{A}$) ≠ ($R_{B}$, $P_{B}$). 모든 i에 대해, 1 ≤ $R_{i}$ ≤ S. 모든 i에 대해, 1 ≤ $P_{i}$ ≤ 2 × $R_{i}$ - 1. 모든 i에 대해, ($R_{i}$, $P_{i}$) ≠ ($R_{A}$, $P_{A}$). 모든 i에 대해, ($R_{i}$, $P_{i}$) ≠ ($R_{B}$, $P_{B}$). 모든 i < C에 대해, $R_{i}$ < $R_{i+1}$이거나, $R_{i}$ = $R_{i+1}$이고 $P_{i}$ < $P_{i+1}$이다.

테스트 세트 1

T = 48. S = 2.

테스트 세트 2

1 ≤ T ≤ 100. 2 ≤ S ≤ 6.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 여섯 정수 S, $R_{A}$, $P_{A}$, $R_{B}$, $P_{B}$, C가 들어 있는 한 줄로 시작한다. 이들은 각각 미술관의 한 변 길이(방의 한 변 길이의 배수), Alma의 시작 방의 행과 위치, Berthe의 시작 방의 행과 위치, 공사 중인 방의 수를 나타낸다. 이어서 C개의 줄이 더 주어진다. 이 줄들을 1부터 세었을 때 i번째 줄에는 두 정수 $R_{i}$와 $P_{i}$가 주어지며, 공사 중인 i번째 방의 행과 위치를 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 위에서 설명한 대로 Alma가 게임에서 보장할 수 있는 최선의 점수이다.

예제 케이스 #1에서는 차례가 다음과 같이 진행되어야 한다.

• Alma가 방 (2, 2)으로 이동한다.

• Berthe는 이동할 수 없다.

• Alma가 방 (2, 3)으로 이동한다.

• Berthe는 여전히 이동할 수 없다.

• Alma는 이동할 수 없다. 어느 화가도 이동할 수 없으므로 이제 게임이 끝난다.

Alma는 방 3개를 칠했고 Berthe는 방 1개를 칠했으므로, 점수는 3 - 1 = 2이다.

예제 케이스 #2에서는 어느 화가도 이동할 수 없다. 두 사람은 자신의 시작 방만 칠한다.

다음 추가 케이스들은 테스트 세트 1에는 나올 수 없지만 테스트 세트 2에는 나올 수 있다.

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

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

• (3, 5)로 이동하면 Alma는 더 이상 이동할 수 없고, Berthe는 계속해서 방을 두 개 더 칠하게 된다. 점수: 2 - 3 = -1.

• Alma가 (3, 3)로 이동하면, Berthe는 다음 중 하나를 할 수 있다.

• (3, 2)로 이동하여 이후 어느 화가도 이동할 수 없게 한다. 점수: 2 - 2 = 0.

• (2, 2)로 이동한다. 그러면 나머지 게임은 다음과 같이 진행되어야 한다. Alma가 (3, 2)로 이동하고, Berthe가 (1, 1)로 이동한다. 점수: 3 - 3 = 0.

So Alma는 (3, 3)로 이동하면 Berthe가 무엇을 하든 점수 0을 보장하며, 이는 (3, 5)로 이동했을 때 얻게 되는 점수 -1보다 낫다는 것을 안다. 따라서 Alma는 (3, 3)로 이동한다. 다음 사항에 유의한다.

• 이 게임의 나머지 부분이 정확히 어떻게 진행될지는 알 수 없지만, Alma가 보장할 수 있는 최선의 점수는 알 수 있다.

• 공사 중이 아닌 방 중 하나 이상이 칠해지지 않을 수도 있다.

케이스 #2에서 Alma는 반드시 (3, 3)로 이동해야 하며, 그다음 Berthe에게는 (2, 2)보다 (3, 4)로 이동하는 것이 더 낫다.