Problem 2279 Cantonese

One day, you went to a locker room. There're n cabinet lined up in this locker room, indexed from 1 to n. At beginning, you stand by the 1st one, and you saw there's one of you Cantonese fellow townsman ("guǎngdōng lǎoxiāng") sit on the bench, and the ith cabinet is i steps away from him. He said, "wǒ yě shì gè guǎngdōngrén, suǒyǐ wǒmen kěnéng shì lǎoxiāng."(I'm a Cantonese too, so we might be fellow townsman.)

You felt confused, so you want to knock some cabinet doors (, and say something). There're m events, the ith event contains two integers ti and xi, means you can knock the xith cabinet doors at the end of the tith second. Knock doesn't cost any time, but you can only move one step per second. For each event, if you missed it, your "guǎngdōng lǎoxiāng" will stand up and walk one step to you. Don’t let him touch you! Now you have to know, how many events can be happening at most before he gets you or you run out of events?

Since you're so clever, we prepared multiple test cases for you.

First line contains an integer T(1 <= T <=100), represents there are T test cases.

For each test case: first line contains two integers, n(1 <= n <=100000) and m(0 <= m <= 100000). Following m lines, the ith line has two integers, ti(1 <= ti<= 1000000000) and xi(1 <= xi<= n). We guarantee that the sum of m for all test cases won’t exceed 300000.

For each test case, output "Case #X: Y" in a line (without quotes), where X is the case number starting from 1, and Y is the maximum number of events which can be happened.

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

Case #1: 1
Case #2: 2
Case #3: 2