Migrated from Lutece 363 Determine

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a strange pipe, which has two entrances, conveniently named the left entrance and the right entrance. You have some weighted balls, which are numbered from $1$ to $N$. Now, you want to push your balls into the strange pipe, ball $1$ first, and then ball $2$, $\cdots$ , and finally ball $N$. When you push a ball in through an entrance, it must heavier than the balls pushed in before through this entrance. You are clever enough to determine which ones you can and should push in, so could you tell me the maximum number of balls you can successfully push into the strange pipe?

Input

The first line of the input is an integer $T$ ($T\leq 50$), which stands for the number of test cases you need to solve.

Every test case begins with an integer $N$ ($N\leq 1000$), the number of balls. And then $N$ integers follow, specify the weight of ball $1$ to ball $N$. Weight is nonnegative and less than $10^9$.

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and starts at $1$. Then output the answer. See sample for more details.

Samples

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

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

Note

You can choose to push a ball in or not even if you can push the ball in successfully.

Resources

The 9th UESTC Programming Contest Preliminary