Divide String into Three Palindromic Parts

You are given a non-empty string s. Determine whether it is possible to split s into three non-empty parts s = s1 + s2 + s3 such that each part is a palindrome. A string is a palindrome if it reads the same forward and backward.

For example, if s = "abacaba", one possible splitting is "a", "bacab", "a", each of which is a palindrome, so the output should be YES. Otherwise, output NO.

Note: The splitting must have three non-empty parts.

inputFormat

The first line contains an integer t (the number of test cases).

Each of the next t lines contains a non-empty string s consisting of lowercase English letters.

outputFormat

For each test case, output a single line containing YES if the string can be divided into three palindromic parts, and NO otherwise.

## sample

5
abacaba
abccba
abcd
aaa
abcbaabcba

YES
YES
NO
YES
YES

</p>