H. Traveling on the Axis
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 , where i is an integer, stands a traffic light of type ti ().

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

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 ≤ |s| ≤ 105, |s| = n, for all 1 ≤ i ≤ |s|), indicating the types of the traffic lights. If , the traffic light at point (i - 0.5) is of type 0 and is initially red; If , 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 106.

Output

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

Example
Input
3
101
011
11010
Output
12
15
43
Note

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.