当前没有测试数据。

CF测试跳转：https://codeforces.com/contest/2241/problem/C

You are given a binary string $s$ consisting only of the characters $\texttt{0}$ and $\texttt{1}$.

In one operation, you can do the following:

• Choose a substring$^{\text{∗}}$ of $s$ that is a palindrome$^{\text{†}}$ of length at least $2$.
• Delete exactly one character from this chosen substring.

The remaining parts of the string are then concatenated to form the new string $s$.

Find the minimum possible length of the string $s$ that can be achieved after applying this operation any number of times (possibly zero).

$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$^{\text{†}}$A string $a$ of length $m$ is said to be palindrome if $a_i = a_{m + 1 - i}$ for all $1 \le i \le m$.

Input

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of each test case follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$. It is guaranteed that each character of $s$ is either $\texttt{0}$ or $\texttt{1}$.

Output

For each test case, print the minimum possible length of the string $s$ that can be achieved after applying the operation any number of times.

Example

4
4
0000
3
110
6
110011
6
101100

1
2
1
1

Note

In the first test case, the initial string is $\texttt{0000}$. We can perform the following sequence of operations:

• Choose the palindromic substring $\texttt{0000}$. Delete one $\texttt{0}$. The string becomes $\texttt{000}$.
• Choose the palindromic substring $\texttt{000}$. Delete one $\texttt{0}$. The string becomes $\texttt{00}$.
• Choose the palindromic substring $\texttt{00}$. Delete one $\texttt{0}$. The string becomes $\texttt{0}$.

The string $\texttt{0}$ contains no palindromic substrings of length at least $2$, so no further operations can be performed. The minimum possible length is $1$.

In the second test case, the initial string is $\texttt{110}$.

• Choose the palindromic substring $\texttt{11}$. Delete one $\texttt{1}$. The string becomes $\texttt{10}$.

The string $\texttt{10}$ contains no palindromic substrings of length at least $2$, so no further operations can be performed. The minimum possible length is $2$.