I I U P C   2 0 1 3

Problem I: Block Meh

 

Everybody knows Korimbai. Though he does not have time for any one. He is a legend in his own.

 

Now once Korimbai got very angry with the puny humans around him. He decided to block them on his social networking website Korimboi. ( Korimboi is very popular website among puny humans, every one of you have 1 or more account on that, though people do not know about the actual creator ( Korimbai ) / actual name ( Korimboi ) of the site, because as always Korimbai has no time for that.)

 

Korimbai is a strange man, so he wants to block them in a strange way. As the creator of korimboi he has this special power of blocking more than 1 people at 1 click. He does that in the following way.

 

He chooses one puny human given that puny human’s entrance and exit time be S1 and E1 respectively in Korimadda (Chat client in Korimboi) and selects it for blocking. Then he finds another puny human whose entrance time and exit time be S2 and E2 respectively. He can select it if and only if S2 > S1 and E2 < E1. Now he search for another puny human whose entrance time and exit time be S3 and E3 respectively and S3 > S2 and E3 < E2. He continues this search until there are nobody available in those criteria that Si  > Si-1 and Ei < Ei-1.  Then he blocks all of them at once in one click.

 

Now Korimbai wants to give this puzzle to you for your brain exercise (of course he knows the answer. He is THE Korimbai, but he has no time for that). He wants to know that given all the entrance and exit time for the puny humans in his korimadda list what is the minimum number of click Korimbai needs to give to delete all of the puny humans of his list.

 

Input

First line of input will contain the number of test cases, T ≤ 20 to follow. In each test case 1st line contains N, number of puny humans in Korimbai’s lists. N line follows each containing 2 integers Si  and Ei, entrance and exit time for the ith puny human

 

N ≤ 20000

0 ≤ Si ≤ Ei ≤ 1000000

 

 

Output

For each input, print the output in the format, Case X: Y (here, X is the serial of the input and Y is the minimum number of click Korimbai needs to give to delete all of the puny humans of his list.

 

 

 

 

 

 

 

Sample Input

Output for Sample Input

2

4

1 5

2 5

3 5

3 4

4

1 5

2 4

3 5

3 3

 

 
Case 1: 3

Case 2: 2

 

Output Explanation

 

On the first test case Korimbai can block 1st à4th puny human in 1 click and 2nd in 1 click and 3rd in 1 click totaling 3 clicks. He cannot do less than that.

 

On the second test case Korimbai can block 1stà2ndà4th puny human in 1 click and 3rd in 1 click totaling 2 clicks. He cannot do less than that.

 

Problem Setter : F. A. Rezaur Rahman

Alternate Solution : Pratyai Mazumder