310282: CF1809D. Binary String Sorting

D. Binary String Sortingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a binary string $s$ consisting of only characters 0 and/or 1.

You can perform several operations on this string (possibly zero). There are two types of operations:

• choose two consecutive elements and swap them. In order to perform this operation, you pay $10^{12}$ coins;
• choose any element from the string and remove it. In order to perform this operation, you pay $10^{12}+1$ coins.

Your task is to calculate the minimum number of coins required to sort the string $s$ in non-decreasing order (i. e. transform $s$ so that $s_1 \le s_2 \le \dots \le s_m$, where $m$ is the length of the string after applying all operations). An empty string is also considered sorted in non-decreasing order.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains the string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting of only characters 0 and/or 1.

The sum of lengths of all given strings doesn't exceed $3 \cdot 10^5$.

Output

For each test case, print a single integer — the minimum number of coins required to sort the string $s$ in non-decreasing order.

ExampleInput

6
100
0
0101
00101101
1001101
11111

Output

1000000000001
0
1000000000000
2000000000001
2000000000002
0

Note

In the first example, you have to remove the $1$-st element, so the string becomes equal to 00.

In the second example, the string is already sorted.

In the third example, you have to swap the $2$-nd and the $3$-rd elements, so the string becomes equal to 0011.

In the fourth example, you have to swap the $3$-rd and the $4$-th elements, so the string becomes equal to 00011101, and then remove the $7$-th element, so the string becomes equal to 0001111.

In the fifth example, you have to remove the $1$-st element, so the string becomes equal to 001101, and then remove the $5$-th element, so the string becomes equal to 00111.

In the sixth example, the string is already sorted.

题目大意：
给定一个只包含字符 '0' 和 '1' 的二进制字符串 s。你可以对字符串进行几种操作（可能为零次），有两种类型的操作：

1. 选择两个连续的元素并交换它们。执行此操作需要支付 \(10^{12}\) 枚硬币；
2. 从字符串中选择任意元素并将其删除。执行此操作需要支付 \(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 按非递减顺序排序所需的最少硬币数。

示例：
输入：
```
6
100
0
0101
00101101
1001101
11111
```
输出：
```
1000000000001
0
1000000000000
2000000000001
2000000000002
0
```

注意：
- 在第一个示例中，你需要删除第一个元素，使字符串变为 "00"。
- 在第二个示例中，字符串已经排序。
- 在第三个示例中，你需要交换第二个和第三个元素，使字符串变为 "0011"。
- 在第四个示例中，你需要交换第三个和第四个元素，使字符串变为 "00011101"，然后删除第七个元素，使字符串变为 "0001111"。
- 在第五个示例中，你需要删除第一个元素，使字符串变为 "001101"，然后删除第五个元素，使字符串变为 "00111"。
- 在第六个示例中，字符串已经排序。题目大意： 给定一个只包含字符 '0' 和 '1' 的二进制字符串 s。你可以对字符串进行几种操作（可能为零次），有两种类型的操作： 1. 选择两个连续的元素并交换它们。执行此操作需要支付 \(10^{12}\) 枚硬币； 2. 从字符串中选择任意元素并将其删除。执行此操作需要支付 \(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 按非递减顺序排序所需的最少硬币数。 示例： 输入： ``` 6 100 0 0101 00101101 1001101 11111 ``` 输出： ``` 1000000000001 0 1000000000000 2000000000001 2000000000002 0 ``` 注意： - 在第一个示例中，你需要删除第一个元素，使字符串变为 "00"。 - 在第二个示例中，字符串已经排序。 - 在第三个示例中，你需要交换第二个和第三个元素，使字符串变为 "0011"。 - 在第四个示例中，你需要交换第三个和第四个元素，使字符串变为 "00011101"，然后删除第七个元素，使字符串变为 "0001111"。 - 在第五个示例中，你需要删除第一个元素，使字符串变为 "001101"，然后删除第五个元素，使字符串变为 "00111"。 - 在第六个示例中，字符串已经排序。