Chiaki 有一个无限长的字符串 $\dots w w^r w w^r \dots$，其中 $w = w_1 w_2 \dots w_m$ 且 $w^r = w_m w_{m-1} \dots w_1$。

Chiaki 从这个无限长的字符串中截取了一个子串 $s = s_1 s_2 \dots s_n$ ($m < n$)。此外，已知 $s$ 中包含 $w$ 或 $w^r$ 作为子串。

之后，Chiaki 忘记了字符串 $w$ 以及它的长度 $m$。她现在只拥有字符串 $s$。她想知道有多少对 $(i, j)$ 满足 $1 \le i \le j \le n$，使得 $s_{i \dots j} = s_i s_{i+1} \dots s_j$ 是 $w$ 或 $w^r$ 的一个可能取值。

输入格式

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

第一行包含一个字符串 $s$ ($2 \le |s| \le 10^6$)，仅由小写英文字母组成。

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

输出格式

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

样例

输入 1

1
aaa

输出 1

5