PTSD

There are $n$ soldiers in the JB kingdom, numbered $1, 2, \cdots, n$. The $i$-th soldier has power value $i$.

A tournament is held in the kingdom. The soldiers must be divided into several groups so that each soldier belongs to exactly one group. A group may contain only one soldier.

Some soldiers have post-traumatic stress disorder (PTSD). A soldier with PTSD is upset if exactly one other soldier in his group has a larger power value than him, that is, he is the second strongest in the group.

JB, the king, wants to maximize the sum of the power values of the upset soldiers. Divide the soldiers to find this maximum.

The first line contains a positive integer $T$, the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of soldiers.

The second line contains a string $s$ of length $n$ consisting of '0' and '1'. The $i$-th character describes the $i$-th soldier. If $s_i$ is '1', the $i$-th soldier has PTSD. Otherwise, the $i$-th soldier does not have PTSD.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output one line containing the maximum sum of the power values of the upset soldiers.

In the first test case, a valid division is [1, 2], [3, 4], [5]. It makes soldiers 1 and 3 upset. The division [1, 2], [3, 5], [4] is also valid.

In the second test case, a valid division is [1, 2], [3, 4], [5, 6], [7, 8].

In the third test case, a valid division is [1, 3], [2, 4].

In the fourth test case, a valid division is [1, 2, 3, 4].