Monocarp 家附近有一家出售人偶的商店。一组新的可动人偶即将发布;该套装包含 $$$n$$$ 人物,第 $$$i$$$ 人物需要 $$$i$$$ 硬币,可从 $$$i$$$ 天到 $$$n$$$ 天购买。
对于 $$$n$$$ 的每一天,Monocarp 都知道他是否可以访问商店。
Monocarp每次访问商店时,他都可以购买商店中出售的任意数量的可动人偶(当然,他不能购买尚未可供购买的可动人偶)。如果 Monocarp 在同一天购买至少两个人物,他将获得等于他购买的最昂贵人物的成本的折扣(换句话说,他免费获得他购买的人物中最昂贵的一个)。
Monocarp 想要购买套装中的第一个 $$$1$$$ 人偶、第一个 $$$2$$$ 人偶、...、第一个 $$$n$$$ 人偶。他不能两次购买同一个模型。他至少要花多少钱?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — 集合中的数字数量(以及天数);
- 第二行包含字符串 $$$s$$$ ($$$|s| = n$$$,每个 $$$s_i$$$ 为 0 或 1)。如果 Monocarp 可以在第 $$$i$$$ 天访问商店,则 $$$s_i$$$ 为 1;否则,$$$s_i$$$ 为 0。
输入的附加限制:
- 在每个测试用例中,$$$s_n$$$ 为 1,因此 Monocarp 始终能够在第 $$$n$$$ 期间购买所有人物;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Monocarp 必须花费的最低金额。
示例
输入 #1
4 1 1 6 101101 7 1110001 5 11111
输出 #1
1 8 18 6
注意
在第一个测试用例中,Monocarp 在 $$$1$$$-st 天购买了 $$$1$$$-st 人物并花费了 $$$1$$$ 硬币。
在第二个测试用例中,Monocarp 可以在 $$$3$$$-rd 天购买 $$$1$$$-st 和 $$$3$$$-rd 图形,在 $$$4$$$-th 天购买 $$$2$$$-nd 和 $$$4$$$-th 图形,在 $$$4$$$-th 天购买 $$$5$$$-th 和 $$$6$$$-th 图形。第 $$$6$$$ 天。然后,他将花费 $$$1+2+5=8$$$ 币。
在第三个测试用例中,Monocarp 可以在第 $$$3$$$-rd 天购买 $$$2$$$-nd 和 $$$3$$$-rd 人物,并在第 $$$7$$$-th 天购买所有其他人物。然后,他将花费 $$$1+2+4+5+6 = 18$$$ 硬币。