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