Naughty Subsequence - V2.0

Mahib loves ‘Naughty Subsequence’-s. He will give you an array of characters ara[0,1,...,n-1] that contains n English capital letters. You need to print the length of the longest Naughty Subsequence of that array.

Now, what is a Naughty Subsequence? The subsequence of an array of characters ara[] is called Naughty when it’s characters are first lexicographically increasing and then decreasing. Even if the subsequence does not have an increasing part (just have the decreasing part), it is called Naughty. In the same way, even if the subsequence does not have a decreasing part (just have the increasing part), it is called Naughty.

Input

The first line of input will be the total number of test cases t (0 < t < 101). You’ll be given the value of n (3 ≤ n ≤ 500) in the first line of each test cases, which is the length of ara[]. And in the second line, you will be given n English capital letters as input, which are the elements of ara[].

Output

For each test case, output the length of the longest Naughty Subsequence of the array provided by Mahib.

Sample

Input	Output
2 8 A K B J D E B A 6 H F C D B A	6 5

In the 1st case: The longest Naughty Subsequence is {A, B, J, D, B, A} and it’s length is 6.
In the 2nd case: The longest Beautiful Subsequence is {H, F, C, B, A} and it’s length is 5.

Problem setter: Mashfiqur R. Khan (mashfiqur404)