JB 王国有 $n$ 名士兵，编号为 $1, 2, \dots, n$。第 $i$ 名士兵的战力值为 $i$。

王国现在举办一场锦标赛。士兵们需要被分成若干个小组，每名士兵必须恰好属于一个小组。注意，允许小组中仅包含一名士兵。

由于某种未知原因，一些士兵患有一种称为 PTSD（创伤后应激障碍）的疾病。患有 PTSD 的士兵不喜欢在小组中成为战力第二强的士兵。形式化地说，如果一名患有 PTSD 的士兵所在的小组中，恰好有一名士兵的战力值比他大，那么这名士兵就会感到沮丧。

JB 王国的国王 JB 想要最大化所有因 PTSD 而感到沮丧的士兵的战力值之和。请你帮助他进行分组。

输入格式

输入包含多组测试数据。第一行包含一个正整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示士兵的人数。

第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 仅包含字符 '0' 和 '1'。第 $i$ 个字符描述第 $i$ 名士兵：如果 $s_i = \text{'1'}$，则第 $i$ 名士兵患有 PTSD；否则，第 $i$ 名士兵没有 PTSD。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示感到沮丧的士兵的战力值之和的最大值。

样例

样例输入 1

4
5
10101
8
11111111
4
1100
4
0110

样例输出 1

4
16
3
3

说明

对于第一组测试数据，一种有效的分组方式是 $[1, 2], [3, 4], [5]$，这使得第 1 名士兵和第 3 名士兵感到沮丧。$[1, 2], [3, 5], [4]$ 也是有效的。

对于第二组测试数据，一种有效的分组方式是 $[1, 2], [3, 4], [5, 6], [7, 8]$。

对于第三组测试数据，一种有效的分组方式是 $[1, 3], [2, 4]$。

对于第四组测试数据，一种有效的分组方式是 $[1, 2, 3, 4]$。