Once I went market to buy a teddy. The shopkeeper offered a puzzle and said he'll give me whatever i wish at a huge discount if i give him the working piece of code for following problem. You will be given a string S of length N, containing either 'A' or 'B'. Make all the possible lists from the given list, with the given operation that you are allowed to change one symbol into another. Then assign maximum weight to each of the string and get the string with maximum weight and return the weight.

You have only following two ways to assign weight to symbol:

1. Pair a S[i] symbol with adjacent one (S[i] or S[i-1]). Each symbol can only be paired with exactly one symbol. Weight of a pair is 4. Pair will be either 'AB' or 'BA'.
2. Keep a S[i] Symbol independent. Weight of unpaired symbol is 1.
3. Each symbol is either involved in exactly one either pair or unpaired status.
4. For each string, keep in mind the number of symbols (K) with index i, 1 <= i <= N, which are changed from original symbol S[i].
5. For each of the possible lists, Add all the weight assigned as a pair and unpair, then subtract K from it. assign this final value as string weight. Add each paired weight once exactly.

The task is to maximize the weight of the string. Suppose S="ABB", possible transforms can be {"ABB", "ABA", "AAB", "AAA", "BBB", "BBA", "BAB", "BAA"} with respective weight {5, 4, 4, 1, 2, 3, 3, 2}. Maximum weight is found 5 in string 1.

Constraints

1 <= N <= 10^5, 1 <= T <= 500.

Input

First line contains t, number of testcases. For each testcase, first line contains N, length of the string. Second line contains string itself.

Output

For each testcase, output the maximum weight of a string that can be obtained.

Example

Input:
5
3
ABB
7
ABBBAAA
8
BAAAAAAA
12
AAAAAAAAAAAA
11
ABABBBABABA

Output:
5
12
13
18
21