给你一个二进制字符串 $$$s$$$,仅包含字符 0 和/或 1。
您可以对此字符串执行多项操作(可能为零)。有两种类型的操作:
- 选择两个连续的元素并交换它们。为了执行此操作,您需要支付 $$$10^{12}$$$ 硬币;
- 从字符串中选择任何元素并将其删除。为了执行此操作,您需要支付 $$$10^{12}+1$$$ 硬币。
你的任务是计算以非递减顺序对字符串 $$$s$$$ 进行排序所需的最小硬币数(即变换 $$$s$$$ 以便 $$$s_1 \le s_2 \le \dots \le s_m$$$,其中 $$$m$$$ 是应用所有操作后字符串的长度)。空字符串也被视为按非降序排序。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$),仅包含字符 0 和/或 1。
所有给定字符串的长度总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 以非递减顺序对字符串 $$$s$$$ 进行排序所需的最小硬币数。
示例
输入 #1
6 100 0 0101 00101101 1001101 11111
输出 #1
1000000000001 0 1000000000000 2000000000001 2000000000002 0
注意
在第一个示例中,您必须删除 $$$1$$$-st 元素,因此字符串变为等于 00。
在第二个示例中,字符串已经排序。
在第三个示例中,您必须交换 $$$2$$$-nd 和 $$$3$$$-rd 元素,因此字符串等于 0011。
在第四个示例中,您必须交换第 $$$3$$$-rd 和第 $$$4$$$-th 元素,因此字符串变为等于 00011101,然后删除第 $$$7$$$-th 元素,因此字符串变为等于 0001111。
在第五个示例中,您必须删除 $$$1$$$-st 元素,因此字符串变为等于 001101,然后删除 $$$5$$$-th 元素,因此字符串变为等于 00111。
在第六个示例中,字符串已经排序。