A good contest must have a good contest name. Busy Beaver has many ideas for how to name his next great programming contest; can you tell him which ones are the best?

A word is a string (of length at least one) containing only uppercase letters. A good contest name is a word that can be written in the form $ABB$ where $A$ and $B$ are words.

You're given $Q$ strings of uppercase letters. For $i=1 \ldots Q$, output "YES" if the $i^\text{th}$ string is a good contest name, and "NO" otherwise.

Input

The first line contains $Q$ ($1 \le Q \le 100$).

The next $Q$ lines contain one string each. Each string consists of between $3$ and $5000$ uppercase letters.

It is guaranteed that the sum of lengths of all strings is at most $5000$.

Output

Output $Q$ lines, the answer for each string. The output is case insensitive, so "YES", "yes", and "Yes", for example, will be treated identically.

Examples

Input 1

5
MITIT
MITIIT
AAA
KLDSJLAJJLAJJ
ABCABC

Output 1

YES
NO
YES
YES
NO

Note

Explanation:

MITIT can be written as [M][IT][IT].

MITIIT cannot be written as $ABB$ for any words $A$ and $B$.

AAA can be written as [A][A][A].

KLDSJLAJJLAJJ can be written as [KLDSJ][LAJJ][LAJJ] or [KLDSJLAJJLA][J][J].

ABCABC cannot be written as $ABB$ for any words $A$ and $B$ ([][ABC][ABC] doesn't count because the first word cannot be empty).