Wavio is a sequence of integers. It has some interesting properties:

1. Wavio is of odd length i.e. L = 2*n + 1.
2. The first (n+1) integers of Wavio sequence make a strictly increasing sequence.
3. The last (n+1) integers of Wavio sequence make a strictly decreasing sequence.
4. No two adjacent integers are same in a Wavio sequence.

For example {1, 2, 3, 4, 5, 4, 3, 2, 1} is an Wavio sequence of length 9. But {1, 2, 3, 4, 5, 4, 3, 2, 2} is not a valid wavio sequence.

In this problem, you will be given a sequence of integers. You have to find the length of the longest Wavio sequence which is a subsequence of the given sequence. For the given sequence: {1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 5, 4, 1, 2, 3, 2, 2, 1} the longest Wavio sequence is: {1, 2, 3, 4, 5, 4, 3, 2, 1}. Thus, the result should be be 9.

Input starts with an integer T (≤ 12), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 10⁵) denoting the number of elements in the sequence. The next line contains N space separated integers between -10⁸ to 10⁸, that form the sequence.

For each case, print the case number and the length of the maximum possible Wavio sequence.

Dataset is huge, use faster I/O methods.