M. Balancing Thomas
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Thomas has been studying physics, and recently he learned about levers and torque. As practice, he has been experimenting by placing identical weights on a lever to see what balances. Since the weights are identical, he can keep track of his setup with a binary string of odd length, where the 1s represent where weights are located, and the middle index is the position under which the lever's fulcrum is located. Thomas's current configuration of weights might not be balanced, and he wants to put in as little effort as possible to extend it to a configuration that will balance.

Formally, we define a binary string to be an equilibrium string if it has odd length and satisfies $$$\sum_{i \in W} (i-m) = 0$$$ where $$$m$$$ is the index of the midpoint of the string and $$$W$$$ is the set of indices having 1s. Given a binary string representing Thomas's current configuration of weights, your task is to find the length of the shortest equilibrium string of which the given string is a prefix.

Below is an example calculation of a binary string that is not an equilibrium string. However, by adding two characters onto the end, it can be made into one. In fact, we cannot turn the first string into an equilibrium string with any shorter extension.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case consists of a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the binary string.

The second line of each test case consists of a single string of length $$$n$$$, where each character is either a 0 or 1.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the length of the shortest equilibrium string of which the given string is a prefix.

Example
Input
5
5
01101
6
100011
3
111
10
1001010110
8
10010000
Output
7
7
3
15
11
Note

For the first test case, the shortest equilibrium string having the input as a prefix is of length 7, and one example is shown in the picture above.

In the second test case, we can convert 100011 into 1000110.

The third test case is already an equilibrium string, so we need not extend it.