你现在身处珠穆朗玛峰顶，想要享受那里所有美好的徒步路线。然而，根据以往的经验，独自在珠穆朗玛峰上攀登并不是个好主意——你可能会在黑暗中迷路！因此，你希望在预定的时间与导游一起徒步。

山上共有 $C$ 个营地（编号为 $1$ 到 $C$），以及 $2 \times C$ 条单向徒步路线（编号为 $1$ 到 $2 \times C$）。每条徒步路线从一个营地出发，到达另一个不同的营地，且中途不经过其他营地。珠穆朗玛峰人烟稀少，生意清淡；每个营地恰好有 $2$ 条徒步路线出发，也恰好有 $2$ 条徒步路线到达。

每条徒步路线每天运行一次。路线 $1$ 和 $2$ 从营地 $1$ 出发，路线 $3$ 和 $4$ 从营地 $2$ 出发，以此类推：通常情况下，路线 $2 \times i - 1$ 和路线 $2 \times i$ 从营地 $i$ 出发。第 $i$ 条徒步路线到达营地 $E_i$，在 $L_i$ 时刻出发，持续时间恰好为 $D_i$ 小时。

当前时刻为 $0$；一天中的时刻编号为 $0$ 到 $23$。你现在位于营地 $1$，想要将每条徒步路线恰好完成一次，并最终回到营地 $1$。

你不能通过除徒步路线以外的任何方式在营地间移动。在营地停留时，你可以等待任意小时数（包括零小时），然后再进行徒步，但你只能在徒步路线出发的瞬间开始该路线。

在查看了路线时刻表后，你确定实现目标是绝对可能的，但你希望尽可能快地完成。如果你最优地规划路线，完成所有徒步路线总共需要多少小时？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $C$：营地的数量。随后有 $2 \times C$ 行。其中第 $i$ 行（从 $1$ 开始计数）表示一条从营地 $\lfloor (i + 1) / 2 \rfloor$ 出发的徒步路线，包含三个整数 $E_i, L_i, D_i$，含义如上所述。注意，此格式保证每个营地恰好有两条路线出发。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是实现目标所需的最少小时数。

数据范围

时间限制：每个测试集 $20$ 秒。 内存限制：$1$ GB。 $1 \le T \le 100$。 $1 \le E_i \le C$。 $E_i \neq \lceil i / 2 \rceil$，对于所有 $i$。（没有徒步路线在同一个营地出发和结束。） 满足 $\{j : E_j = i\}$ 的集合大小为 $2$，对于所有 $j$。（每个营地恰好有两条路线到达。） $0 \le L_i \le 23$。 $1 \le D_i \le 1000$。 保证至少存在一条从营地 $1$ 出发并回到营地 $1$，且包含每条徒步路线恰好一次的路径。

样例

样例输入 1

2
2
2 1 5
2 0 3
1 4 4
1 6 3
4
3 0 24
2 0 24
4 0 24
4 0 24
2 0 24
1 0 24
3 0 24
1 0 24

样例输出 1

Case #1: 32
Case #2: 192

说明 1

在样例 #1 中，最优计划如下： 在营地 $1$ 等待 $1$ 小时，直到时刻 $1$。 在时刻 $1$ 离开营地 $1$ 进行 $5$ 小时的徒步路线；在时刻 $6$ 到达营地 $2$。 立即在时刻 $6$ 离开营地 $2$ 进行 $3$ 小时的徒步路线；在时刻 $9$ 到达营地 $1$。 在营地 $1$ 等待 $15$ 小时，直到下一天的时刻 $0$。 在时刻 $0$ 离开营地 $1$ 进行 $3$ 小时的徒步路线；在时刻 $3$ 到达营地 $2$。 在营地 $2$ 等待 $1$ 小时，直到时刻 $4$。 * 在时刻 $4$ 离开营地 $2$ 进行 $4$ 小时的徒步路线；在时刻 $8$ 到达营地 $1$。

这在 $1$ 天 $8$ 小时（即 $32$ 小时）内实现了目标。任何其他计划所需时间更长。

在样例 #2 中，所有路线都在同一时间出发且持续时间相同。完成任何路线后，你可以立即进行下一条路线。如果我们按路线在测试用例中出现的顺序将其编号为 $1$ 到 $8$，则一种最优计划为：$1, 5, 4, 7, 6, 2, 3, 8$。