PALDR - Even Palindrome

no tags 

Palindrome is a string that has the property of reading the same in either direction (left to right or right to left). You are to determine whether a given string can be expressed as a concatenation of palindromes of even length.

Note: A string can be formed by concatenation of any number of even palindrome strings.

Input

First line contains T (T < 100), the number of test cases. T lines follow, each containing the string corresponding to that particular test case.

Note:

There might be a new-line character (i.e. '\r' in C++) at the end of each line. Be careful with your languages.

Output

Output consists of T lines, one corresponding to each test case. You should output YES if the string can be expressed as concatination of even length palindromes and NO otherwise.

Example

Input:
3
madam
aA
aabb

Output:
NO
NO
YES 

Constraints

Length of string ≤ 106


hide comments
Eddy Cael: 2015-10-18 04:24:03

Be careful with '\r' at end of lines. Cost me some WA. if you can find all the palindromes, so you can get AC with greedy algorithm...

GHOST_YO: 2015-06-28 08:37:44

if there is a string of length 0, would the ans be yes or no??
For eg. if input is 2\r\n\r\naabb\r\n
should i print YES
YES

or NO
YES

Eddy Cael: 2014-09-08 06:07:35

Brute Force is wonderful... :D

Amit: 2012-09-26 05:13:39

@author :
Please look at my submission (7719444),
and tell whether it is a problem with IO or with my algorithm.

:D: 2012-09-23 19:34:23

Please read fitcat post before trying do this problem:
http://www.spoj.pl/forum/viewtopic.php?f=3&t=10277&p=30925&hilit=PALDR#p31195

This is really bad when you have an input guessing game. There probably are empty lines, '\r' sings and even valid white characters in the input files. The solver must get lucky to interpret correctly, what is part of the query string and what is not. If you're making a problem like this, at the very least make all input strings non-empty with no white characters. Then it can be read by simple tokenization. Either that or make REALLY sure to clean the input files.

lxyxynt: 2012-08-29 18:39:31

Even you know there would be '\r',please be sure that you replace it with 0..

Ðộc cô cầu bại: 2011-05-11 00:59:21

I can't believe that I 've just used basic algorithm to accept this problem with 0.49s

Ninjaflyte: 2010-06-18 18:12:43

I considered reading '\r' and also accepted zero length strings, but still my prog gets WA. Is there only one '\r' per line? And is there anything else to be taken care of in the input?? (like whitespaces, etc.)

Last edit: 2010-06-18 18:15:02
Pranay: 2010-04-14 07:41:01

is aAaA considered YES or NO?

Andrei Grigorean: 2009-11-20 08:07:06

Be very careful at the way you read. Try the example with '\r' before each '\n' - like Tony Beta Lambda showed. Also, there are strings of length 0. You should consider them valid palindromes.

Last edit: 2009-11-20 08:07:28

Added by:Race with time
Date:2009-02-19
Time limit:0.240s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Code Craft 09