PALDR - Even Palindrome

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


Được gửi lên bởi:Race with time
Ngày:2009-02-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:Code Craft 09

hide comments
2016-01-31 13:10:07
Bài này phần dịch sang tiếng Việt bị lỗi font rồi. Mong AD sửa lại.
2014-12-22 20:48:33 Anh Duc Le
C++ chú ý cái '/r' ở cuối xâu.
2014-12-08 04:14:10 m
Bài này T giới hạn bao nhiêu mà dùng HASH lại TLE vậy? :(
2014-10-17 15:25:47 Hướng Thái Dương
time chặt quá :'(
2014-10-16 18:22:06 Change The World
bài này ai gợi ý thuật toán đê :3
khó vl!!!!!!
2013-08-14 07:54:11 Stupider
input trong c++ khoai vãi =.=

Last edit: 2013-08-14 14:00:39
2012-02-23 09:59:45 Thắng 20 cm
bai nay QHD phai ko cac ban
2011-06-14 07:10:32 Le Viet Thanh Long
Minh dung thuat toan co ban de giai bai nay ma van AC thu 2 ve mat thoi gian =))
2009-04-08 05:36:02 Thiêm Nguyễn
Manacher Algorithm. :)

Last edit: 2009-04-08 15:37:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.