Description

dd is playing a cut-sequence game. It gives a sequence of N numbers a[1], a[2], … a[N]. dd can remove at most two consecutive fragments. Then he computes the length of the longest consecutive increasing subsequence. What is the maximum possible length he can get?

Input

The first line of the input is an integer T (T <= 100), which stands for the number of test cases you need to solve.

Each test case begins with an integer N (1 <= N <= 10^5) indicating the size of the sequence.

I ensure that 90% of the test data will satisfy N<=1000.

The next line contains N integers a[1], a[2], …, a[N] (0 <= a[i] <= 10^9, 1<=i<=N).

Output

For every test case, you should output "Case #k: " first, where k indicates the case number and starts at 1. Then output the maximum possible length of consecutive increasing subsequence after remove at most two consecutive fragments.

Sample

Input

2
4
1 2 3 4
12
10 1 2 7 9 3 4 8 8 5 6 1

Output

Case #1: 4
Case #2: 6

Hint

For the 2nd Case, we can remove 2 fragments 7 9 and 8 8, and get sequence 10 1 2 3 4 5 6 1. So the longest subsequence is 1 2 3 4 5 6.