PAUWS - Pair and unpair weightest string

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

ID RESULT TIME
code...



Added by:Rishav Goyal
Date:2014-04-09
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2023-08-31 22:13:10
@author would you like to have a look at my submission id:31776292, please, and tell me whats wrong with my algorithm
thanks

Last edit: 2023-08-31 22:14:34
2016-01-24 14:58:54 mohit
Easy question, ACC in one go :)


Last edit: 2016-01-24 15:00:05
2015-08-26 16:08:49
AC in one Go! :D 0.28ms
2014-08-14 22:20:49 Akhilesh Anandh
Time limit too strict.. had to use faster IO methods to get accepted.
2014-08-14 22:20:49 P_Quantum
Nice DP ..!!
2014-08-14 22:20:49 anurag garg
@author can you have a look at my submission id:11468949 and tell me whats wrong with my algorithm
thanks

Reply : @anurag : Try this testcase,

1
20
ABBBBBBBBBBBBBBBAAAAAAAAAAAAAAAAAAA

AC Actual Output : 31.

EDIT...your test case is wrong it should have 20 characters
atleast provide some valid test case

EDIT: I am already getting 31 for the testcase that you have provided

Last edit: 2014-04-20 18:45:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.