题目描述

在灵霄峰脚下有一间神秘的法宝阁。近日，阁中即将上架一套极为珍稀的灵偶法宝，这套法宝共有 $n$ 件，每件都蕴含着独特且强大的灵力。其中，第 $i$件灵偶法宝需耗费 $i$枚灵晶方可兑换，且仅在开阁后的第 $i$ 日至第 $n$ 日这段时间面向修仙者开放兑换。

修仙者逸风一心想要集齐这套灵偶法宝，锤炼自身功法。对于这 $n$ 天中的每一天，逸风凭借自身灵识掐算，便能知晓当日法宝阁是否对外开放，让他得以入内兑换法宝($0$ 代表不能入内，$1$代表可以入内)。

每次逸风踏入法宝阁，他能够选取阁中正在开放兑换的任意数量灵偶法宝（自然，尚未到兑换时间的，他即便法力高深也无法染指）。法宝阁有个不成文却人人皆知的特惠规则，若逸风在同一天兑换至少两件灵偶法宝，便能免去其中价值最高那件法宝所需的灵晶，相当于免费获取了最贵的那件。

逸风志在必得，定要从这套法宝里精准地兑换一个第 1 件、一个第 2 件、……、一个第$n$件灵偶法宝，绝不可重复兑换同一件。究竟他最少需要耗费多少灵晶，才能如愿以偿呢？

输入格式

第一行包含一个整数 $t$—— 测试用例的数量。

每个测试用例由两行组成：

• 第一行包含一个整数 $n$—— 这套灵偶法宝中的法宝数量（以及天数）；
• 第二行包含一个字符串 $s$（每个 $s_i$ 要么是$0$要么是$1$）。若逸风在第 $i$ 天可进入法宝阁，那么 $s_i$ 便是$1$；反之，$s_i$ 即为 $0$ 。

关于输入的额外限制条件：

• 在每个测试用例中， $s_n$ 是 $1$ ，意味着逸风总能在第 $s_n$ 天进入法宝阁兑换所有法宝；

输出格式

$T$ 行，每行输出一个数字代表最小花费。

数据样例

输入数据

4
1
1
6
101101
7
1110001
5
11111

输出数据

1
8
18
6

提示

在第一个测试用例中，逸风在第 1 天兑换第 1 件灵偶法宝，耗费 1 枚灵晶。

在第二个测试用例中，逸风可在第 3 天兑换第 1 件和第 3 件灵偶法宝，在第 4 天兑换第 2 件和第 4 件灵偶法宝，在第 6 天兑换第 5 件和第 6 件灵偶法宝。如此一来，他将耗费 1+2+5 = 8枚灵晶。

在第三个测试用例中，逸风能在第 3 天兑换第 2 件和第 3 件灵偶法宝，在第 7 天兑换其余所有灵偶法宝。这般操作后，他需耗费 1+2+4+5+6=18 枚灵晶。

数据范围

对于 $100\%$ 的数据：$1 <=t <=10^4,n（1<=n<=4\times10^5）$ ,所有测试用例中 $n$ 的总和不超过 $10^6$