Submit Best Submissions All Submissions

73. Password Patterns


Problem Statement:
Ahmed M El-Sayed is the head of systems in the Arab Collegiate Programming Contest (his colleagues used to call him compiler shortened as compo, that goes back to his college days when he used to quickly predict the output of different programs without compiling and running them). Each year in the ACPC he pick some pattern or rule so that all passwords used by the teams should follow. This year the pattern is as follows: For a string S, if it can be divided into at least 2 contiguous non-overlapping substrings, so that each occurrence of a unique substring is replaced by a unique character, S would be palindrome.

For example, string "abcdqwrtrqwabcd" can be segmented into "abcd-qw-r-t-r-qw-abcd", then we replace segment "abcd" with character 'A', segment "qw" with character 'B', segment "r" with character 'C', and segment "t" with character 'D'

We would end up with a new string "ABCDCBA" which is palindrome, so string "abcdqwrtrqwabcd" can be a password.

Given some candidate strings, can you help him find out if they can be passwords or not?


Input Format:
Your program will be tested on one or more test-cases. The first line of the input will be a single integer T, the number of test-cases (1 ≤ T ≤ 100). Followed by T test-cases.

Each test case is on a line containing N lowercase English characters, representing a possible password. The length of each string is at least 1 and at most 105


Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1), followed by a space then "YES" or "NO" according to whether it can be a password or not.


Sample Input:
2 abcabc abcxyz


Sample Output:
Case 1: YES Case 2: NO





Added by: ahmed_aly
Added at: 2014-04-27 04:51:48 UTC
Time Limit: 3 seconds
Partial score: No
Source:ACM Jordanian Collegiate Programming Contest 2013