Codeforces Round 849 (Div. 4) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

implementation

two pointers

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Prepend and Append

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTimur initially had a binary string$$$^{\dagger}$$$ $$$s$$$ (possibly of length $$$0$$$). He performed the following operation several (possibly zero) times:

- Add $$$\texttt{0}$$$ to one end of the string and $$$\texttt{1}$$$ to the other end of the string. For example, starting from the string $$$\texttt{1011}$$$, you can obtain either $$$\color{red}{\texttt{0}}\texttt{1011}\color{red}{\texttt{1}}$$$ or $$$\color{red}{\texttt{1}}\texttt{1011}\color{red}{\texttt{0}}$$$.

$$$^{\dagger}$$$ A binary string is a string (possibly the empty string) whose characters are either $$$\texttt{0}$$$ or $$$\texttt{1}$$$.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of testcases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the length of Timur's final string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{0}$$$ or $$$\texttt{1}$$$, denoting the final string.

Output

For each test case, output a single nonnegative integer — the shortest possible length of Timur's original string. Note that Timur's original string could have been empty, in which case you should output $$$0$$$.

Example

Input

931004011151010161010107101011011210211101011011010

Output

1 2 5 0 3 1 0 2 4

Note

In the first test case, the shortest possible string Timur started with is $$$\texttt{0}$$$, and he performed the following operation: $$$\texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}}$$$.

In the second test case, the shortest possible string Timur started with is $$$\texttt{11}$$$, and he performed the following operation: $$$\texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}}$$$.

In the third test case, the shortest possible string Timur started with is $$$\texttt{10101}$$$, and he didn't perform any operations.

In the fourth test case, the shortest possible string Timur started with is the empty string (which we denote by $$$\varepsilon$$$), and he performed the following operations: $$$\varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}}$$$.

In the fifth test case, the shortest possible string Timur started with is $$$\texttt{101}$$$, and he performed the following operations: $$$\texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}}$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 16:27:17 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|