AOJ 4717 - Three Palindromes

Three Palindromes

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on HDU. Original ID: 5340
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

Description

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

Input

First line contains a single integer $T \leq 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\leq |s| \leq 20000$

Output

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

Sample Input

2
abc
abaadada

Sample Output

Yes
No

Source

BestCoder Round #49 ($)