Alice 喜欢收集邮票。她现在正在邮局购买一些新邮票。

世界上存在 $N$ 种不同的邮票，编号为 $1$ 到 $N$。然而，邮票不是单独出售的，必须成套购买。现有 $M$ 种不同的邮票套装；第 $i$ 套包含编号从 $L_i$ 到 $R_i$ 的邮票。同一种邮票可能出现在多个套装中，也可能存在一种或多种邮票在任何套装中都不包含的情况。

所有套装的价格相同；由于 Alice 的预算有限，她最多只能购买 $K$ 个不同的套装。请问 Alice 最多能得到多少种不同的邮票？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含三个整数：$N$、$M$ 和 $K$，分别表示可用的不同邮票种类数、可用的邮票套装数以及 Alice 最多能购买的套装数。

接下来有 $M$ 行，第 $i$ 行表示第 $i$ 个邮票套装，包含两个整数 $L_i$ 和 $R_i$，表示该套装中包含的邮票编号的闭区间。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Alice 最多能得到的不同邮票种类数。

数据范围

• $1 \le T \le 100$
• $1 \le K \le M$
• $1 \le N, M \le 2000$
• $1 \le L_i \le R_i \le N$

样例

输入 1

2
5 3 2
3 4
1 1
1 3
100 2 1
1 50
90 100

输出 1

Case #1: 4
Case #2: 50

说明

在样例 #1 中，Alice 可以购买第 1 套和第 3 套邮票，它们包含了前 4 种邮票。注意，她虽然得到了两张编号为 3 的邮票，但只计算不同种类的邮票数量，而不计算每种邮票的数量。

在样例 #2 中，Alice 可以购买第 1 套邮票，其中包含 50 种不同的邮票。