Do you know Professor Saeed? He is the algorithms professor at Damascus University. Yesterday, he gave his students hard homework (he is known for being so evil) - for a given binary string $S$, they should compute the sum of $F(S, L, R)$ over all pairs of integers $(L, R)$ ($1 \le L \le R \le |S|$), where the function $F(S, L, R)$ is defined as follows:
- Create a string $U$: first, set $U = S$, and for each $i$ ($L \le i \le R$), flip the $i$-th character of $U$ (change '1' to '0' or '0' to '1').
- Then, $F(S, L, R)$ is the number of valid pairs $(i, i + 1)$ such that $U_i = U_{i+1}$.
As usual, Professor Saeed will give more points to efficient solutions. Please help the students solve this homework.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$.

-----Output-----
For each test case, print a single line containing one integer $\sum_{1 \le L \le R \le |S|} F(S, L, R)$.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le |S| \le 3 \cdot 10^6$
- the sum of $|S|$ over all test cases does not exceed $6 \cdot 10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $1 \le |S| \le 300$
- the sum of $|S|$ over all test cases does not exceed $600$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
001

-----Example Output-----
6

-----Explanation-----
Example case 1:
- $L = 1, R = 1$: $U$ is "101", $F = 0$
- $L = 2, R = 2$: $U$ is "011", $F = 1$
- $L = 3, R = 3$: $U$ is "000", $F = 2$
- $L = 1, R = 2$: $U$ is "111", $F = 2$
- $L = 2, R = 3$: $U$ is "010", $F = 0$
- $L = 1, R = 3$: $U$ is "110", $F = 1$

见题面

见题面