A function on a binary string T of length M is defined as follows:

F(T) = number of indices $i \ (1 \le i \lt M)$ such that $T_i \neq T_{i+1}.$

You are given a binary string S of length N. You have to divide string S into two subsequences $S_1, S_2$ such that:

• Each character of string S belongs to one of $S_1$ and $S_2$.
• The characters of $S_1$and $S_2$.must occur in the order they appear in S.

Find the maximum possible value of $F(S_1) + F(S_2).$

NOTE: A binary string is a string that consists of characters `0` and `1`. One of the strings $S_1$, $S_2$ can be empty.

Input format

• The first line contains T denoting the number of test cases. The description of T test cases is as follows:
• For each test case:
  • The first line contains N denoting the size of string S.
  • The second line contains the string S.

Output format
For each test case, print the maximum possible value of $F(S_1) + F(S_2)$ in a separate line.

Constraints

$1 \leq T \leq 10^5 \\ 1 \leq N \leq 10^5\\ \mid S \mid = N\\ S\; contains \; characters \ '0' \ and\ '1'.\\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;2\cdot 10^5.$