Description

Can we divided a given string S into three nonempty palindromes?

题意：给出一个字符串，问能否将字符串分为三段，并且每一段的是回文串。

Format

Input

First line contains a single integer T≤20 which denotes the number of test cases.

For each test case , there is an single line contains a string S which only consist of lowercase English letters.1≤|s|≤20000

Output

For each case, output the "Yes" or "No" in a single line.

Samples

2
abc
abaadada

Yes
No