题目描述

$ZJC$王国有 $n$ 名士兵，编号为 $1, 2, \dots, n$。第 $i$ 名士兵的力量值为 $i$。 现在王国里有一场比武比赛。士兵们需要被分成若干组，每个士兵只能属于一个组。注意：一个组可以只包含一个士兵。

由于某种未知原因，一些士兵患有一种名为 PTSD（创伤后应激障碍）的疾病。患有 PTSD 的士兵不喜欢成为他们所在组中的第 2 强士兵。具体来说，如果一个患有 PTSD 的士兵在他所在组中有且仅有 1 名比他力量值更大的士兵，他会感到不安。

$ZJC$希望最大化因 PTSD 感到不安的士兵的力量值总和。请你帮助他分配士兵。

输入格式

• 第一行包含一个正整数 $T$，表示测试用例的数量。
• 对于每个测试用例：
  • 第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示士兵的数量。
  • 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 '0' 和 '1' 组成。
    第 $i$ 个字符描述第 $i$ 名士兵：
    • 若 $s_i = \texttt{'1'}$，则第 $i$ 名士兵患有 PTSD。
    • 若 $s_i = \texttt{'0'}$，则第 $i$ 名士兵没有 PTSD。

数据范围：所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行一个整数，表示因 PTSD 感到不安的士兵的力量值总和的最大值。

样例

4
5
10101
8
11111111
4
1100
4
0110

4
16
3
3

• 第 1 个测试用例：一种有效分组为 $[1,2]$、$[3,4]$、$[5]$，使得第 1 名士兵和第 3 名士兵感到不安。
  另一种有效分组为 $[1,2]$、$[3,5]$、$[4]$，结果相同。