H. 回文串分割
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个字符串，请判断其是否能被表示为若干个回文串拼接的结果。

形式化的说：

一个字符串 $$$S$$$ 是回文的，当且仅当其从前往后和从后往前读相同。

一个字符串 $$$S$$$ 是好的，当且仅当存在某个 $$$n \geq 1$$$ 使得 $$$ S = T_1 T_2 \cdots T_n$$$ ，其中 $$$T_i(1 \le i \le n)$$$ 是回文串。

给定字符串 $$$S$$$ ，请判断其是否是好的字符串。

Input

输入包含多组数据。

第一行一个整数 $$$T(1 \le T \le 10^6)$$$ ，表示数据的组数。

接下来 $$$T$$$ 行，每行一个字符串 $$$S$$$ ($$$1 \le |S| \leq 10^6$$$，$$$S$$$ 仅包含小写英文字母) ，表示被询问的串。

数据保证 $$$\sum |S| \le 5 \times 10^6$$$ ，其中 $$$|S|$$$ 表示字符串 $$$S$$$ 的长度。

Output

对于每组数据，若其是好的字符串，输出 'Yes' ，否则输出 'No' 。

Example
Input
2
sosos
hahaha
Output
Yes
Yes
Note

'sosos' 本身就是回文的，因此输出 'Yes' 。

'hahaha' 可以被划分为 'hah' 和 'aha' ，二者都是回文串，因此输出 'Yes' 。