你正在进行一项规定的举重训练。训练包含一系列必须按顺序完成的练习。每个练习都需要在机器上放置一组特定的杠铃片。

共有 $W$ 种不同的杠铃片。例如，一个练习可能需要 3 个 A 类杠铃片和 1 个 B 类杠铃片，而下一个练习可能需要 A、C、D 类杠铃片各 2 个。

杠铃片以堆叠的形式放置在机器上。形式上，通过单次操作，你可以将任意类型的杠铃片添加到堆叠顶部，或者移除当前位于堆叠顶部的杠铃片。

你可以按任意顺序将每个练习所需的杠铃片装载到机器的堆叠上。因此，如果你在上述示例的第一个练习中将 B 类杠铃片放在最底部，那么在进行第二个练习之前，你必须先取下所有杠铃片。另一方面，如果你将 B 类杠铃片放在从底部数第三个位置，你就可以保留底部的两个 A 类杠铃片，使其成为下一个练习所需集合的一部分，从而节省时间。

给定每个练习所需的每种杠铃片的数量，求出完成所有练习所需的最少操作次数。你必须按给定的顺序完成练习。机器的堆叠初始为空，并且在完成所有练习后，堆叠必须再次为空。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $E$ 和 $W$：练习的数量和杠铃片的种类数。杠铃片种类编号为 $1$ 到 $W$。接下来有 $E$ 行。其中第 $i$ 行包含 $W$ 个整数 $X_{i,1}, X_{i,2}, \dots, X_{i,W}$，表示第 $i$ 个练习恰好需要 $X_{i,j}$ 个 $j$ 类杠铃片。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是完成所有练习所需的最少机器堆叠操作次数。

数据范围

$1 \le T \le 100$。 $1 \le X_{i,1} + X_{i,2} + \dots + X_{i,W}$，对于所有 $i$。（每个练习至少需要一个杠铃片。）

测试集 1（可见判定）

$1 \le E \le 10$。 $1 \le W \le 3$。 $0 \le X_{i,j} \le 3$，对于所有 $i, j$。

测试集 2（隐藏判定）

$1 \le E \le 100$。 $1 \le W \le 100$。 $0 \le X_{i,j} \le 100$，对于所有 $i, j$。

样例

样例输入 1

3
3 1
1
2
1
2 3
1 2 1
2 1 2
3 3
3 1 1
3 3 3
2 3 3

样例输出 1

Case #1: 4
Case #2: 12
Case #3: 20

说明

在样例 1 中，只有一种类型的杠铃片。第一个练习需要 1 个，第二个需要 2 个，第三个需要 1 个。你可以通过 4 次操作完成练习，步骤如下：

1. 向堆叠添加一个杠铃片。完成第一个练习。
2. 向堆叠添加一个杠铃片。完成第二个练习。
3. 从堆叠顶部移除一个杠铃片。完成第三个练习。
4. 从堆叠顶部移除一个杠铃片。此时堆叠变为空。

在样例 2 中，完成练习的一种操作次数为 12 的方式如下：

1. 添加一个 2 类杠铃片。
2. 添加一个 3 类杠铃片。
3. 添加一个 1 类杠铃片。
4. 添加一个 2 类杠铃片。此时堆叠从底到顶包含的杠铃片类型为 2, 3, 1, 2。完成第一个练习。
5. 从堆叠顶部移除一个 2 类杠铃片。
6. 添加一个 3 类杠铃片。
7. 添加一个 1 类杠铃片。此时堆叠从底到顶包含的杠铃片类型为 2, 3, 1, 3, 1。完成第二个练习。
8. 从堆叠顶部移除一个 1 类杠铃片。
9. 从堆叠顶部移除一个 3 类杠铃片。
10. 从堆叠顶部移除一个 1 类杠铃片。
11. 从堆叠顶部移除一个 3 类杠铃片。
12. 从堆叠顶部移除一个 2 类杠铃片。此时堆叠变为空。