Problem Description

You are given $N$ intervals. An interval can be represented by $2$ positive integers $L_i$ and $R_i$ - the interval starts at $L_i$ and ends at $R_i$, represented as $[L_i, R_i]$. Intervals may not be unique, so there might be multiple intervals with both equal $L_i$ and equal $R_i$.

You are allowed to perform a maximum of $C$ cuts. A cut at $X$ will cut all intervals $[L, R]$ for which $L < X$ and $X < R$. Cutting an interval at $X$ is defined as splitting the interval into $2$ intervals - $[L, X]$ and $[X, R]$. Note that cuts can only be performed at integer points. Also, cutting at an endpoint of an interval ($X = L$ or $X = R$) has no effect and does not split the interval.

You need to find the maximum number of intervals that can be obtained through a maximum of $C$ cuts.

Input Format

The first line of the input contains the number of test cases, $T$. $T$ test cases follow.

Each test case starts with a line containing $2$ integers, $N$ and $C$, denoting the number of intervals and the maximum number of cuts you can perform respectively. $N$ lines follow.

The $i$-th line contains $2$ integers, $L_i$ and $R_i$, describing the $i$-th interval.

Output Format

For each test case, output one line containing Case $\#x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the maximum number of intervals that can be obtained through at most $C$ cuts, as described above.

1
3 3
1 3
2 4
1 4

Case #1: 7

Hint

In the provided sample, cuts should be performed at $2$ and $3$ to get the maximum number of intervals.

After the first cut at $2$, the intervals would be $\{[1, 2], [2, 3], [2, 4], [1, 2], [2, 4]\}$.

After the second cut at $3$, the intervals would be $\{[1, 2], [2, 3], [2, 3], [3, 4], [1, 2], [2, 3], [3, 4]\}$.

It can be seen that no interval can be cut further, so the answer is $7$.

Limits

Memory limit: $1$ GB.

$1 \le T \le 100$.

Test Set $1$

$1 \le N \le 500$.

$1 \le C \le 10^5$.

$1 \le L_i < R_i \le 10^4$ for all $i$.

Test Set $2$

$1 \le N \le 10^5$.

$1 \le C \le 10^{18}$.

$1 \le L_i < R_i \le 10^{13}$ for all $i$.