You are given intervals. An interval can be represented by positive integers and - the interval starts at and ends at , represented as . Intervals may not be unique, so there might be multiple intervals with both equal and equal .
You are allowed to perform a maximum of cuts. A cut at will cut all intervals for which and . Cutting an interval at is defined as splitting the interval into intervals - and . Note that cuts can only be performed at integer points. Also, cutting at an endpoint of an interval ( or ) 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 cuts.
输入格式
The first line of the input contains the number of test cases, . test cases follow.
Each test case starts with a line containing integers, and , denoting the number of intervals and the maximum number of cuts you can perform respectively. lines follow.
The -th line contains integers, and , describing the -th interval.
输出格式
For each test case, output one line containing Case : , where is the test case number (starting from ) and is the maximum number of intervals that can be obtained through at most cuts, as described above.
样例
样例输入 1
1
3 3
1 3
2 4
1 4
样例输出 1
Case #1: 7
数据范围与提示
In the provided sample, cuts should be performed at and to get the maximum number of intervals.
After the first cut at , the intervals would be .
After the second cut at , the intervals would be .
It can be seen that no interval can be cut further, so the answer is .
