The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online (The 2nd Universal Cup. Stage 1: Qingdao) |
---|
Finished |
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:
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
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.
For each test case output one line containing one integer, indicating the answer.
3
101
011
11010
12
15
43
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.
Name |
---|