Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4054
Traveling on the Axis

Time Limit: 1 Second      Memory Limit: 65536 KB

BaoBao is taking a walk in the interval $[0, n]$ on the number axis, but he is not free to move, as at every point $(i - 0.5)$ for all $i \in [1, n]$, where $i$ is an integer, stands a traffic light of type $t_i$ ($t_i \in \{0, 1\}$).

BaoBao decides to begin his walk from point $p$ and end his walk at point $q$ (both $p$ and $q$ are integers, and $p < q$). During each unit of time, the following events will happen in order:

  1. Let's say BaoBao is currently at point $x$, he will then check the traffic light at point $(x + 0.5)$. If the traffic light is green, BaoBao will move to point $(x + 1)$; If the traffic light is red, BaoBao will remain at point $x$.

  2. All the traffic lights change their colors. If a traffic light is currently red, it will change to green; If a traffic light is currently green, it will change to red.

A traffic light of type 0 is initially red, and a traffic light of type 1 is initially green.

Denote $t(p, q)$ as the total units of time BaoBao needs to move from point $p$ to point $q$. For some reason, BaoBao wants you to help him calculate $$\sum_{p=0}^{n-1}\sum_{q=p+1}^n t(p, q)$$ where both $p$ and $q$ are integers. Can you help him?

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains a string $s$ ($1 \le |s| \le 10^5$, $|s| = n$, $s_i \in \{\text{'0'}, \text{'1'}\}$ for all $1 \le i \le |s|$), indicating the types of the traffic lights. If $s_i = \text{'0'}$, the traffic light at point $(i - 0.5)$ is of type 0 and is initially red; If $s_i = \text{'1'}$, the traffic light at point $(i - 0.5)$ is of type 1 and is initially green.

It's guaranteed that the sum of $|s|$ of all test cases will not exceed $10^6$.

Output

For each test case output one line containing one integer, indicating the answer.

Sample Input

3
101
011
11010

Sample Output

12
15
43

Hint

For the first sample test case, it's easy to calculate that $t(0, 1) = 1$, $t(0, 2) = 2$, $t(0, 3) = 3$, $t(1, 2) = 2$, $t(1, 3) = 3$ and $t(2, 3) = 1$, so the answer is $1 + 2 + 3 + 2 + 3 + 1 = 12$.

For the second sample test case, it's easy to calculate that $t(0, 1) = 2$, $t(0, 2) = 3$, $t(0, 3) = 5$, $t(1, 2) = 1$, $t(1, 3) = 3$ and $t(2, 3) = 1$, so the answer is $2 + 3 + 5 + 1 + 3 + 1 = 15$.


Author: WENG, Caizhi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
Submit    Status