CF2026C.Action Figures

在 Monocarp 家附近有一家商店，专门售卖手办。近期，这家店将推出一套新的手办系列，总共包含 $n$ 个手办。其中，第 $i$ 个手办的价格为 $i$ 枚金币。在第 $i$ 天到第 $n$ 天之间，这个手办都是可以购买的。

Monocarp 知道他在这 $n$ 天中的哪几天可以去商店。

每次去商店的时候，他可以购买多件手办（当然，不能买尚未发售的手办）。如果他在同一天购买了至少两个手办，他可以享受一个折扣：他所购买的最贵手办是免费的，也就是说他无需为该手办支付费用。

Monocarp 的目标是从这个手办系列中，分别购买一个第 $1$ 个手办、一个第 $2$ 个手办……一直到一个第 $n$ 个手办。注意，每个手办只能购买一次。请你帮他计算，他最少需要花费多少金币？

第一行输入一个整数 $t$，表示有多少个测试用例（$1 \le t \le 10^4$）。

每个测试用例包含两行：

• 第一行是一个整数 $n$，表示手办的数量（也是销售天数）（$1 \le n \le 4 \cdot 10^5$）；
• 第二行是一个长度为 $n$ 的字符串 $s$。如果在第 $i$ 天 Monocarp 可以去商店，$s_i$ 就为 1；否则为 0。

额外的限制条件有：

• 在每个测试用例中，字符串 $s$ 的最后一个字符 $s_n$ 一定是 1，所以 Monocarp 无论如何都能在最后一天买到所有手办。
• 所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$。

对每个测试用例，输出一个整数，表示 Monocarp 最少需要花费的金币数。

在第一个测试用例中，Monocarp 可以在第一天购买第一个手办，花费 1 枚金币。

在第二个测试用例中，他可以在第三天购买第 1 和第 3 个手办，在第四天购买第 2 和第 4 个手办，在第六天购买第 5 和第 6 个手办。这样总费用为 $1+2+5=8$ 枚金币。

在第三个测试用例中，他可以在第三天购买第 2 和第 3 个手办，其余手办在第七天购买，最终花费 $1+2+4+5+6 = 18$ 枚金币。

本翻译由 AI 自动生成