#L. JIXMPII5JUgT100#-`]

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

Let's define a cyclic shift of some string $s$ as a transformation from $s_1 s_2 \dots s_{n-1} s_{n}$ into $s_{n} s_1 s_2 \dots s_{n-1}$ . In other words, you take one last character $s_n$ and place it before the first character while moving all other characters to the right.

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

In one operation, you can choose any substring $s_l s_{l+1} \dots s_r$ ( $1 \le l < r \le |s|$ ) and cyclically shift it. The cost of such operation is equal to $r - l + 1$ (or the length of the chosen substring).

You can perform the given operation any number of times. What is the minimum total cost to make $s$ sorted in non-descending order?

Format

Input

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

The first and only line of each test case contains a binary string $s$ ( $2 \le |s| \le 2 \cdot 10^5$ ; $s_i \in$ {0, 1}) — the string you need to sort.

Additional constraint on the input: the sum of lengths of strings over all test cases doesn't exceed $2 \cdot 10^5$ .

Output

For each test case, print the single integer — the minimum total cost to make string sorted using operation above any number of times.

Sample

ShanghaiTech ACM 炸鱼杯

未参加

状态: 已结束
规则: OI
题目: 46
开始于: 2024-12-10 23:00
结束于: 2024-12-15 13:00
持续时间: 110 小时
主持人: _Arahc_
参赛人数: 112

#L. JIXMPII5JUgT100#-`]

JIXMPII5JUgT100#-`]

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

#L. JIXMPII5JUgT100#-`]

JIXMPII5JUgT100#-`]

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

还没有账户？

登录