A. MITIT
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Check out Python input/output or C++ input/output or Java input/output for reading in the input numbers.

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.

Example
Input
5
MITIT
MITIIT
AAA
KLDSJLAJJLAJJ
ABCABC
Output
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).