Alternating String ~ WildLife-TK

A binary string is called alternating if no two adjacent characters of the string are equal. Formally, a binary string

T

of length

M

is called alternating if

T_{i} \neq T_{i + 1}

for each

1 \leq i < M

For example, 0, 1, 01, 10, 101, 010, 1010 are alternating strings while 11, 001, 1110 are not.

You are given a binary string $S$

of length

N

. You would like to rearrange the characters of

S

such that the length of the longest alternating substring of

S

is maximum. Find this maximum value.

A binary string is a string that consists of characters 0 and 1. A string $a$

is a substring of a string

b

a

can be obtained from

b

by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input Format

The first line of input contains an integer $T$

, denoting the number of test cases. The

T

test cases then follow:

The first line of each test case contains an integer

N

The second line of each test case contains the binary string

S

Output Format

For each test case, output the maximum possible length of the longest alternating substring of $S$

after rearrangement.

Constraints

$1 \leq T \leq 10^{4}$

1 \leq N \leq 10^{5}

S

contains only the characters 0 and 1.

Sum of

N

over all test cases does not exceed

2 \cdot 10^{5}

Sample Input 1

Sample Output 1

Explanation

Test case $1$

: Swapping the second and third characters makes

S = 101

. Hence the length of the longest alternating substring is

3

(choosing the entire string as a substring).

Test case $2$

: The given string

S = 1010

is an alternating string of length

4

Test case $3$

: The length of the longest alternating substring is

1

for any rearrangement of

S = 0000

Test case $4$

: One possible rearrangement of

S

1 \underline{10101} 1

, which has an alternating substring of length

5

(the substring starting at index

2

and ending at index

6