1109: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 t_i and x_i, means you can knock the x_ith cabinet doors at the end of the t_ith 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, t_i(1 <= t_i <= 1000000000) and x_i(1 <= x_i <= 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

        For the first sample, you can only get the first knock. the second one is too far, and then, your Cantonese fellow townsman blocks the third one.

For the second sample, you can do the first knock, and move to the second cabinet to get the third one.

For the third sample, you have to run hurry to get the second knock, and the third one. You can’t get the forth event, because you Cantonese fellow townsman has already been here.