题目描述

小水獭来到沈阳旅游，它认为一个字符串 $s$ 是 SHENYANG 的当且仅当存在两个非空字符串 $a$ 和 $b$ 满足如下三个条件：

• $a$ 由小写字母组成，且 $a$ 中每种字母只出现了一次。
• $b$ 由小写字母组成，且 $b$ 是回文串，也就是说将 $b$ 翻转后得到的字符串和 $b$ 相同。
• 将 $a$ 和 $b$ 顺序拼接得到的字符串和 $s$ 相同，也就是说 $s = a + b$。

例如 henan 是 SHENYANG 的，因为 henan=he+nan，此外也可分解为 hena+n。但 hhnan 和 ysmihoyocom 不是 SHENYANG 的。

现在给定一个字符串，请你帮助小水獭判断它是不是 SHENYANG 的。

输入格式

本题包含多组数据。

• 第一行包含一个整数 $T$（$1 \leq T \leq 10^3$），表示数据组数。
• 对于每组数据： 一行包含一个由小写字母组成的字符串 $s$（$1 \leq |s| \leq 10^5$），表示小水獭询问的字符串。
• 保证所有数据的 $\sum |s| \leq 10^5$。

输出格式

对于每组数据： 输出一行包含一个字符串。如果 $s$ 是 SHENYANG 的，输出 YES；否则输出 NO。

Samples

HENAN

YES

Limitation

1s, 1024KiB for each test case.