你负责管理一个铁路网络。该网络由 $N$ 个车站组成。每个车站 $i$ 需要向恰好另一个车站 $D_i$ 发送货物。车站 $i$ 将通过一列火车发送恰好 $C_i$ 节铁路货车车厢。

你提前获得了所有的运输信息，因此你计划通过重复利用铁路货车车厢来节省成本。如果车站 $i$ 向车站 $D_i$ 发送了 $n$ 节铁路货车车厢，那么如果车站 $D_i$ 尚未进行其自身的运输，它就可以将这些车厢加入到自己的供应中以供使用。

形式上，你必须为每个车站提供初始的铁路货车车厢供应（某些车站可能获得 $0$ 节），并提供一个运输顺序，使得在车站 $i$ 必须进行运输时，其初始供应与之前到达 $i$ 的任何运输所带来的车厢数量之和，至少等于它自身运输所需的车厢数量 $C_i$。你不能从车站 $i$ 发出超过 $C_i$ 节车厢的运输，即使该车站拥有的车厢多于 $C_i$。

例如，假设车站 $1$ 向车站 $4$ 发送了一列载有恰好 $3$ 节铁路货车车厢的火车。现在，如果车站 $4$ 需要 $2$ 节车厢，它可以重复利用从车站 $1$ 接收到的 $3$ 节车厢中的 $2$ 节。如果车站 $4$ 随后需要发送 $5$ 节车厢，它可以重复利用从车站 $1$ 接收到的所有 $3$ 节车厢，并加上 $2$ 节它自己的初始供应。注意，当车站 $4$ 需要发送 $2$ 节车厢时，它不能发送从车站 $1$ 接收到的全部 $3$ 节车厢。

给定运输信息，为了能够按某种顺序完成所有运输，你需要分配给各车站的初始铁路货车车厢总数最少是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含 $3$ 行。第一行包含一个整数 $N$，表示网络中的车站数量。第二行包含 $N$ 个整数 $D_1, D_2, \dots, D_N$，第三行包含 $N$ 个整数 $C_1, C_2, \dots, C_N$。这些数据表示车站 $i$ 必须向车站 $D_i$ 发送一列恰好包含 $C_i$ 节铁路货车车厢的火车。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是为了完成所有运输而需要分配给各车站的初始铁路货车车厢的最小总数。

数据范围

$1 \le T \le 100$ $1 \le D_i \le N$，对于所有 $i$ $D_i \neq i$，对于所有 $i$ $1 \le C_i \le 10^9$，对于所有 $i$

子任务 1

$2 \le N \le 8$

子任务 2

$2 \le N \le 10^5$

样例

输入格式 1

3
4
2 3 4 3
4 3 2 1
4
2 3 4 1
1 3 1 3
7
3 5 2 5 3 7 6
3 4 6 3 5 1 2

输出格式 1

Case #1: 4
Case #2: 5
Case #3: 10

说明

在样例 #1 中，一种最优方法是按出发车站递增的顺序进行运输。这需要向车站 $4$ 发送 $4$ 节车厢。但在此之后，每个车站都收到了足够的车厢用于其自身的运输，总共需要 $4$ 节。由于没有车厢到达车站 $1$，它肯定需要初始的 $4$ 节，因此这也是可能的最小值。

在样例 #2 中，一种最小化方法是向车站 $3$ 提供 $1$ 节车厢，向车站 $2$ 和 $4$ 各提供 $2$ 节车厢，总共 $5$ 节。然后，我们可以从运输 $3 \to 4$ 开始，这为车站 $4$ 带来了一节额外的车厢。这使得车站 $4$ 拥有了它发送 $4 \to 1$ 所需的 $3$ 节车厢。车站 $1$ 现在拥有 $3$ 节车厢，足以用 $1$ 节车厢完成 $1 \to 2$ 的运输，使车站 $2$ 的总车厢数达到 $3$ 节，足以完成最后的运输 $2 \to 3$。注意，运输 $1 \to 2$ 不能为车站 $2$ 带来额外的车厢，即使有可用的车厢且这样做会有帮助。还有其他方法可以用 $5$ 节初始车厢完成所有运输，但没有办法用更少的车厢完成。

在样例 #3 中，一种最优的初始车厢数量是车站 $1$ 和 $4$ 各 $3$ 节，车站 $5$ 和 $7$ 各 $2$ 节。