PALDR - Even Palindrome

Giới hạn
  • Thời gian: 0.24s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 ≤ 10 6

  • Người up: racer
  • Nguồn bài: Code Craft 09