Election Day has arrived in Bangladesh. The citizens are aware of the fact that the candidates will poster the entire country, ruining the walls, pillars and windows. Thus they have decided to limit the entire election campaign to a single dedicated wall. Every candidate will be allowed to hang exactly one poster on the wall. All posters extend from top to bottom, but are hung at different points on the wall, and can have different width. The wall is divided horizontally into sections, and a poster completely occupies one or more adjacent sections.
But the candidates used the wall without considering the posters from other candidates. Some of the posters were covered (partially or completely) by those of other candidates. Now you are given the location of all the posters and the order in which they were hung, determine how many posters have at least one visible section in the end.
Input
Input starts with an integer T (≤ 8), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 105) denoting the number of posters. Each of the next n lines contains two integers li ri (1 ≤ li ≤ ri ≤ 2*n) denoting the number of the wall section occupied by the left end and the right end of the ith poster, respectively. The input order corresponds to the order of hanging posters.
Output
For each case, print the case number and the number of posters with visible sections.
Sample
| Sample Input | Sample Output |
|---|---|
1 5 1 4 2 6 8 10 3 4 7 10 | Case 1: 4 |
Notes
- Dataset is huge. Use faster I/O methods.
- Illustration for sample input:
