생일 케이크

생일 케이크에 해당하는 $\mathbf{R}$개의 행과 $\mathbf{C}$개의 열로 이루어진 격자가 주어진다. 행은 위에서부터 $1$에서 $\mathbf{R}$까지 번호가 매겨져 있다. 열은 왼쪽에서부터 $1$에서 $\mathbf{C}$까지 번호가 매겨져 있다. 격자의 각 칸은 크기가 $1 \times 1$인 정사각형이다. 케이크에서 가장 맛있는 부분이 하나의 채워진 직사각형을 이룬다는 것을 알아냈다. 즉, 이 직사각형 내부의 모든 칸은 맛있는 부분이고, 직사각형 외부의 모든 칸은 맛있는 부분이 아니다. 길이가 최대 $\mathbf{K}$인 직선 절단을 할 수 있을 만큼 긴 칼이 있다.

맛있는 각 칸에 초를 꽂고 생일 파티를 즐길 수 있도록, 일련의 절단을 통해 맛있는 칸들을 각각 따로 떼어 내려고 한다. 맛있는 각 칸을 따로 떼어 내려면 그 칸은 다른 모든 칸과 연결되어 있지 않아야 한다. 어떤 칸도 $4$개 방향(위, 아래, 왼쪽, 오른쪽) 중 어느 방향으로도 다른 칸과 연결되어 있지 않으면 그 칸은 분리되어 있다.

절단은 방향이 있는 선분이며, 다음 조건을 만족할 때 유효하다.

• 절단은 격자의 행과 열 사이에 있는 수평선이나 수직선 중 하나를 따라 진행된다.

• 절단의 길이는 $\mathbf{K}$을 초과해서는 안 된다.

• 절단의 시작점과 끝점은 격자점(즉, 칸의 꼭짓점)이어야 한다. 또한 시작점은 이미 노출되어 있어야 한다. 즉, 격자의 $4$개 변 중 하나 또는 이전 절단 중 하나 위에 있어야 한다.

• 절단은 다른 노출된 점을 통과해서는 안 된다. 노출된 점에 닿을 수는 있지만, 닿는다면 바로 그 지점에서 끝나야 한다.

$\mathbf{K} = 4$라고 하자. 아래에서 유효한 절단의 예 다섯 개를 볼 수 있다.

다음은 유효하지 않은 절단의 예 네 개이다.

• 첫 번째 그림에서는 절단이 너무 길다($4$보다 길다).

• 두 번째 그림에서는 절단이 노출되지 않은 점(격자의 $4$개 변 중 어느 것에도 속하지 않고 이전 절단에도 속하지 않는 점)에서 시작한다.

• 세 번째 그림에서는 절단이 노출된 점을 통과한다. 길이 $2$에서 노출된 점에 닿는 즉시 멈춰야 한다.

• 네 번째 그림은 세 번째 그림과 같은 이유로 유효하지 않다.

맛있는 모든 칸을 떼어 내는 데 필요한 최소 절단 횟수를 구해야 한다.

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{r_1} \le \mathbf{r_2} \le \mathbf{R}$. $1 \le \mathbf{c_1} \le \mathbf{c_2} \le \mathbf{C}$.

테스트 세트 1

$1 \le \mathbf{R}, \mathbf{C} \le 100$. $\mathbf{K} = 1$.

테스트 세트 2

$1 \le \mathbf{R}, \mathbf{C} \le 10^5$. $1 \le \mathbf{K} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 세 정수 $\mathbf{R}$, $\mathbf{C}$, $\mathbf{K}$가 포함된 줄로 시작한다. 다음 줄에는 맛있는 직사각형의 왼쪽 위 칸과 오른쪽 아래 칸을 각각 나타내는 네 정수 $\mathbf{r_1}$, $\mathbf{c_1}$, $\mathbf{r_2}$, $\mathbf{c_2}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 최소 절단 횟수이다.

추가 예제 - 테스트 세트 2

예제 케이스에서 최소 절단 횟수는 $5$이다. 가능한 절단 순서 중 하나는 다음과 같다.

추가 예제 케이스에서 최소 절단 횟수는 $3$이다. 가능한 절단 순서 중 하나는 다음과 같다.