CodeChef : LOC Aug 2017 – Princess and Beauty

By | August 25, 2017

Princess and Beauty

Source: CodeChef

We all know that the princess is very beautiful but one day jealous from her beauty, a person asked a question from princess in order to check her wisdom. Since princess is not good at programming you need to help her in solving the problem.
You are given a string of length N. You have to check among all the the substrings that whether a substring exist or not which is palindrome and having length greater than 1. If such a substring exists then print YES else print NO.

Input

The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing a string.

Output

For each test case, output a single line containing the YES or NO.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 100000

 

Subtasks

 

Subtask #1 (20 points), Time limit : 1 sec
1 ≤ T<=10, N<=1000 

Subtask #2 (80 points), Time limit : 1 sec
1 ≤ T<=10, N<=100000

Example

Input:
2
ab
babba
Output:
NO
YES

Explanation

Example case 1.The only substring whose length is greater than 1 is ab, and its not a palindrome.

Example case 2.abba is a substring of the string and its a palindrome thus YES.

Solution:

Hint: Pretty easy solution with the combination of optimized palindrome code.