题目描述

给定一个 $R$ 行 $C$ 列的网格，代表一块生日蛋糕。

行从上到下编号为 $1$ 到 $R$，列从左到右编号为 $1$ 到 $C$。网格中的每个单元格都是 $1 \times 1$ 的正方形。

你发现蛋糕中最美味的部分形成了一个单一的实心矩形；也就是说，该矩形内部的所有单元格都是美味的，而矩形外部的所有单元格都不是美味的。

你有一把足够长的刀，可以进行长度不超过 $K$ 的直线切割。

我们希望进行一系列切割，将每个美味单元格单独分离出来，以便在上面放蜡烛，享受生日聚会。

为了单独分离每个美味单元格，它们必须与任何其他单元格断开连接。如果一个单元格在上下左右四个方向都没有与其他单元格相连，则称该单元格是断开的。

切割是一条有向线段，如果满足以下条件，则是有效的：

• 切割沿着网格的行与列之间的水平或垂直直线进行。
• 切割的长度不得超过 $K$。
• 切割的起点和终点必须是格点（即单元格的角点）。此外，起点必须是已经暴露的，即位于网格的四个边之一或之前的某条切割上。
• 切割不得穿过任何其他暴露点。它可以接触暴露点，但如果接触，则必须恰好在此结束。

假设 $K = 4$。下面给出了五个有效切割的示例。

:::align{center} :::

以下是四个无效切割的示例。

:::align{center} :::

• 第一张图中，切割太长（超过 $4$）。
• 第二张图中，切割从未暴露的点开始（既不是网格的四个边也不是之前的切割）。
• 第三张图中，切割穿过了暴露点，它应该在长度为 $2$ 触及暴露点时停止。
• 第四张图无效的原因与第三张图相同。

我们需要找出分离所有美味单元格所需的最少切割次数。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含三个整数 $R$、$C$ 和 $K$。

下一行包含四个整数 $r_1$、$c_1$、$r_2$、$c_2$，分别表示美味矩形的左上角和右下角单元格。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最少切割次数。

1
3 3 1
2 2 2 2

Case #1: 5

1
2 3 4
2 1 2 2

Case #1: 3

提示

在样例中，最少切割次数为 $5$。一种可能的切割序列如下：

:::align{center} :::

在附加样例中，最少切割次数为 $3$。一种可能的切割序列如下：

:::align{center} :::

限制条件

$1 \le T \le 100$。

$1 \le r_1 \le r_2 \le R$。

$1 \le c_1 \le c_2 \le C$。

测试集 1

$1 \le R, C \le 100$。

$K = 1$。

测试集 2

$1 \le R, C \le 10^5$。

$1 \le K \le 10^5$。

翻译由 DeepSeek V4 Pro 完成