One day, Chef prepared D brand new dishes. He named the i-th dish by a string Si. After the cooking, he decided to categorize each of these D dishes as special or not.

A dish Si is called special if it's name (i.e. the string Si) can be represented in the form of a double string by removing at most one (possibly zero) character from it's name from any position.

A string is called a double string if it can be represented as a concatenation of two identical, non-empty strings.
e.g. "abab" is a double string as it can be represented as "ab" + "ab" where + operation denotes concatenation.
Similarly, "aa", "abcabc" are double strings whereas "a", "abba", "abc" are not.

Input

First line of the input contains an integer D denoting the number of dishes prepared by Chef on that day.
Each of the next D lines will contain description of a dish.

The i-th line contains the name of i-th dish Si.

Output
For each of the D dishes, print a single line containing "YES" or "NO" (without quotes) denoting whether the dish can be called as a special or not.

Constraints

1 ≤ D ≤ 10^6
1 ≤ |Si| ≤ 10^6.
Each character of string Si will be lower case English alphabet (i.e. from 'a' to 'z').

Example
Input:
3
aba
abac
abcd

Output:
YES
NO
NO

Explanation
Example case 1.
We can remove the character at position 1 (0-based index) to get "aa" which is a double string. Hence, it is a special dish.
Example case 2.
It is not possible to remove the character at any of the position to get the double string. Hence, it is not a special dish.

见题面

见题面