当前没有测试数据。

题目描述

Sam 为了切割羊腿，特意买了一台很大的羊腿切割机！

这台切割机有一个工作台，现在 Sam 已经把一堆羊腿放在工作台上了。

工作台是个二维平面，但是 Sam 会把所有的羊腿放置到与工作台下边缘平行。

工作台的两侧边缘上分别标注了坐标点 $1,2,3 \dots$

现在 Sam 将 $n$ 只羊腿放置在了工作台上，第 $i$ 只羊腿会放在横向第 $i$ 行上，并且两端刚好对齐工作台的坐标点 $x,y(x < y)$。

例如有 $3$ 只羊腿，分别对齐的坐标点为：$[1,3],[2,4],[1,4]$。

如下图用 $-$ 表示羊腿，这里是上述 $3$ 只羊腿的摆放形状。

1 ----- 
2   -----
3 -------
  1 2 3 4 5

每次切割时 Sam 会设定一个坐标点 $a$，切割机将从上往下把所有经过的羊腿全部切开。

例如上述例子，设定坐标点 $3$ 进行切割，显然这次切割对于三个羊腿将会造成：

1. 刚好经过 $1$ 号羊腿的右端点，所以不会切割 $1$ 号羊腿。
2. 会将 $2$ 号羊腿 $[2,4]$ 切割成 $[2,3],[3,4]$ 两块。
3. 将$3$ 号羊腿 $[1,4]$ 切割成 $[1,3],[3,4]$ 两块。

那么这一次切割后 Sam 将拥有 $5$ 块羊腿。

现在 Sam 将会进行 $m$ 次切割，他想获得尽可能多的块数，该如何切割？最多能切出几块羊腿？

输入格式

本题采用多组测试数据。

第一行一个整数 $T$ 表示测试数据数量，接下来对于每组测试数据有：

第一行包含两个整数 $n,m$ 表示羊腿数量和切割次数。

接下来 $n$ 行每行两个整数 $x_i,y_i$ 表示第 $i$ 只羊腿的放置位置。

输出格式

对于每组测试数据，输出一行形为 Case #A: B 的答案。

其中 $A$ 表示测试数据编号（从 $1$ 开始）, $B$ 表示 Sam 能获得的最多羊腿块数。

输入输出样例 #1

输入 #1

2
3 1
1 3
2 4
1 4
3 3
1 3
2 4
1 4

输出 #1

Case #1: 5
Case #2: 7 

说明/提示

数据范围

对于所有数据满足：$1 \leq T \leq 10$。

样例解释

对于第二组测试数据，Sam 可以依次切割坐标 $2,3,4$ 可以获得最多的羊腿数量。