BaoBao 正在数轴上的区间 $[0, n]$ 内行走，但他不能自由移动，因为在所有 $i \in [1, n]$ 的点 $(i - 0.5)$ 处，都设有一个类型为 $t_i$ ($t_i \in \{0, 1\}$) 的交通灯。

BaoBao 决定从点 $p$ 出发，并在点 $q$ 结束他的行程（$p$ 和 $q$ 均为整数，且 $p < q$）。在每一个单位时间内，以下事件会按顺序发生：

1. 假设 BaoBao 当前位于点 $x$，他会检查点 $(x + 0.5)$ 处的交通灯。如果交通灯是绿色的，BaoBao 将移动到点 $(x + 1)$；如果交通灯是红色的，BaoBao 将停留在点 $x$。
2. 所有交通灯改变颜色。如果交通灯当前是红色的，它将变为绿色；如果交通灯当前是绿色的，它将变为红色。

类型为 0 的交通灯初始为红色，类型为 1 的交通灯初始为绿色。

记 $t(p, q)$ 为 BaoBao 从点 $p$ 移动到点 $q$ 所需的总单位时间。BaoBao 希望你帮他计算：

$$\sum_{p=0}^{n-1} \sum_{q=p+1}^{n} t(p, q)$$

其中 $p$ 和 $q$ 均为整数。你能帮帮他吗？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个字符串 $s$ ($1 \le |s| \le 10^5$, $|s| = n$, $s_i \in \{'0', '1'\}$ 对于所有 $1 \le i \le |s|$)，表示交通灯的类型。如果 $s_i = '0'$，则点 $(i - 0.5)$ 处的交通灯类型为 0，初始为红色；如果 $s_i = '1'$，则点 $(i - 0.5)$ 处的交通灯类型为 1，初始为绿色。

保证所有测试数据的 $|s|$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行包含一个整数，表示答案。

样例

样例输入 1

3
101
011
11010

样例输出 1

12
15
43

说明

对于第一组样例，容易计算出 $t(0, 1) = 1, t(0, 2) = 2, t(0, 3) = 3, t(1, 2) = 2, t(1, 3) = 3$ 以及 $t(2, 3) = 1$，因此答案为 $1 + 2 + 3 + 2 + 3 + 1 = 12$。

对于第二组样例，容易计算出 $t(0, 1) = 2, t(0, 2) = 3, t(0, 3) = 5, t(1, 2) = 1, t(1, 3) = 3$ 以及 $t(2, 3) = 1$，因此答案为 $2 + 3 + 5 + 1 + 3 + 1 = 15$。