你正在尝试组织一群滑雪者。滑雪者们将前往一座租用了一整天的大山。

山上共有 $N$ 个休息点，编号从 $1$ 到 $N$，它们由 $N-1$ 条坡道连接。每条坡道从某个休息点出发，直接通往另一个休息点，中间没有其他坡道或休息点。坡道只能单向通行。

每位滑雪者从山顶休息点出发，穿过一条坡道到达另一个休息点。从那里，滑雪者可以穿过另一条坡道到达下一个休息点，以此类推。一旦滑雪者到达他们的目的地休息点，他们就会停止当天的滑雪，前往滑雪小屋喝热可可。目的地休息点不能是山顶休息点。然而，请注意，滑雪者的目的地休息点可以是零条或多条坡道的起点；也就是说，滑雪者不一定非要一直使用可用的坡道直到无路可走：他们总是可以小心地步行下山！对于所有休息点，滑雪者从山顶休息点到达该点都只有唯一的一条坡道序列。

每条坡道每天只能容纳一定数量的滑雪者，超过该数量后，雪地会变得过于崎岖而无法滑行。此外，滑雪场可以针对滑雪者经过的每条坡道收取费用或给予奖励。每条坡道可能有不同的价格，每位滑雪者必须为他们滑过的每条坡道支付价格。坡道的价格可以是正数、零，甚至是负数；负数价格代表测试该坡道所获得的奖励。作为组织者，你代表你的滑雪者团队支付所有坡道价格并收取所有奖励。请注意，如果多名滑雪者使用同一条坡道，你需要多次支付该坡道的价格或多次收取该坡道的奖励。你支付的所有费用总和减去你收取的奖励总和即为此次行程的总开销。开销可以是正数、零或负数。负数开销意味着你实际上在这次行程中赚到了钱！

作为组织者，你想要算出你能安排上山的滑雪者的最大数量。此外，你还想算出在滑雪者数量达到最大值的情况下，行程的最小可能开销。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$：山上的休息点数量。

每个测试用例的最后 $N-1$ 行通过四个整数 $U_i, V_i, S_i$ 和 $C_i$ 描述一条坡道。它们分别是坡道的起点休息点、终点休息点、坡道可容纳的滑雪者最大数量，以及每位滑雪者通过该坡道的价格。

滑雪者出发的山顶休息点编号始终为 $1$。

输出格式

对于每个测试用例，输出一行，包含 Case #x: y z，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是滑雪者的最大数量，$z$ 是让 $y$ 名滑雪者每人至少滑过一条坡道时的最小开销。

数据范围

时间限制：每个测试集 30 秒。 内存限制：1GB。 $1 \le U_i \le N$，对于所有 $i$。 $2 \le V_i \le N$，对于所有 $i$。（没有坡道可以通向山顶休息点。） $U_i \neq V_i$，对于所有 $i$。 $1 \le S_i \le 10^5$，对于所有 $i$。 $-10^5 \le C_i \le 10^5$，对于所有 $i$。 对于所有 $r$，从山顶休息点到达休息点 $r$ 的坡道序列是唯一的。

子任务 1

$1 \le T \le 100$。 $2 \le N \le 1000$。

子任务 2

$T = 17$。 $2 \le N \le 10^5$。

样例

样例输入 1

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

样例输出 1

Case #1: 4 18
Case #2: 7 15

说明 1

在样例 1 中，我们可以派遣一名滑雪者到休息点 4，一名滑雪者到休息点 3，两名滑雪者到休息点 2。

在样例 2 中，我们可以派遣三名滑雪者到休息点 2，两名滑雪者到休息点 5，两名滑雪者到休息点 4。

请注意，测试用例中列出的第一条坡道不一定非要从山顶休息点开始，且坡道可以满足 $U_i > V_i$。