你创建了一个即将开放的过山车。它的列车由一排 $N$ 个座位组成，从前到后编号为 $1$ 到 $N$。当然，越靠前的座位越有价值。顾客已经购买了开业当天的票。每张票允许特定的顾客在特定的座位上乘坐一次过山车。有些顾客可能购买了多张票，他们期望每张票都能乘坐一次。

你需要决定开业当天会有多少次过山车运行。在每次运行中，每个座位最多可以坐一名顾客；某些座位在一次运行中可能会空着。你不能在同一次运行中将一名顾客分配到多个座位，也不能在同一次运行中将两名顾客安排在同一个座位上。

你希望最小化满足所有票据所需的运行次数，以降低运营成本。为了减少所需的运行次数，你可以对任意数量的票据进行“升级”。升级票据意味着将顾客的票据换成一张座位更靠前（即编号更小）的新票据。你倾向于尽可能少地升级票据，因为过多的升级可能会导致顾客变得贪婪，并在未来要求更多的升级。

给定所有已售出票据的位置和购买者，在需要时进行尽可能多的升级并最优地安排运行的情况下，满足所有票据所需的最小运行次数是多少？为了达到该运行次数，所需的最小票据升级次数又是多少？注意，例如将某位顾客在某次运行中的座位从 $4$ 号升级到 $2$ 号，仅算作一次升级，而不是两次独立的升级。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$（过山车的座位数）、$C$（潜在顾客的数量）和 $M$（已售出的票据数量）。顾客的编号为 $1$ 到 $C$。接下来有 $M$ 行，每行包含两个整数：$P_i$（第 $i$ 张票分配的过山车座位位置）和 $B_i$（该票据购买者的编号）。

输出格式

对于每个测试用例，输出一行 Case #x: y z，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在最优安排运行并使用升级的情况下满足所有票据所需的最小运行次数，$z$ 是为了以 $y$ 次运行满足所有票据而需要进行的最小升级次数。

数据范围

$1 \le T \le 100$ $2 \le N \le 1000$ $1 \le M \le 1000$ $1 \le P_i \le N$ $1 \le B_i \le C$

样例

样例输入 1

5
2 2 2
2 1
2 2
2 2 2
1 1
1 2
2 2 2
1 1
2 1
1000 1000 4
3 2
2 1
3 3
3 1
3 3 5
3 1
2 2
3 3
2 2
3 1

样例输出 1

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

说明

注意，最后两个样例不会出现在小数据集中。

在 Case #1 中，两位顾客都购买了 $2$ 号座位的票。仅用一次运行无法满足两张票，但将其中任意一张票升级到 $1$ 号座位，就可以在同一轮中满足两张票。

Case #2 的情况类似，只是两张票都是 $1$ 号座位的。由于你不能升级这些票或将其换成更差的座位，你被迫进行 $2$ 次单独的运行，每位顾客一次。

Case #3 的特点是同一位顾客购买了两个位置的票。由于你被迫为该顾客进行 $2$ 次运行，因此没有理由进行任何升级。

在 Case #4 中，请注意可能存在没有分配票据的顾客和位置。在这种情况下，有三张票售给了 $3$ 号位置。例如，如果你将顾客 $2$ 升级到 $2$ 号位置，你可以进行一次运行，让顾客 $1$ 坐在 $2$ 号位置，顾客 $3$ 坐在 $3$ 号位置；第二次运行让顾客 $2$ 坐在 $2$ 号位置，顾客 $1$ 坐在 $3$ 号位置。

额外的升级不会让你减少运行次数，因为顾客 $1$ 有两张票，无论位置如何，你都需要在不同的运行中满足这些票。

在 Case #5 中，一种最优解是将其中一张 $3$ 号位置的票升级到 $1$ 号位置。