Một xâu được gọi là xâu đối xứng nếu đọc xâu đó từ trái sang phải hoặc đọc từ phải sang trái đều như nhau. Ví dụ: \("aba", "adccda", "aa"\) là xâu đối xứng. Còn \("abc", "xyzy", "nbk"\) không là xâu đối xứng.

Cho xâu \(s\) có độ dài \(N\) và chỉ bao gồm các chữ cái latin in thường, hãy xác đinh xem có tồn tại một xâu con liên tiếp của \(s\) có độ dài chẵn và là xâu đối xứng hay không. Nói cách khác, nếu kí hiệu \(|s|\) là độ dài của xâu \(s\), hãy xác đinh xem có tồn tại hai chỉ số \(i\) và \(j\) sao cho:

• \(1 \lt i \lt j \lt |s|\).
• \(j — i + 1\) là một số chẵn.
• \(s_i,s_{i+1},\dots,s_j\) là một xâu đối xứng.

Input

• Dòng đầu tiên ghi một số nguyên dương \(T\) - số bộ dữ liệu vào \((T \lt 5)\).
• \(T\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s (|s| \lt 10^5)\) tương ứng với bộ dữ liệu thứ \(i\).

Output

• Với mỗi bộ dữ liệu, nếu tồn tại một xâu con liên tiếp của \(s\) có độ dài chẵn và là xâu đối xứng thì in ra "YES". Ngược lại thì in ra "NO".

Example

Input

2
kbaaaakac
dfsasad

Output

YES
NO

Giải thich

• ở ví dụ thứ nhất, một trong các xâu con liên tiếp có độ dài chẵn và là xâu đối xứng là "aaaa". Đáp án là "YES".
• ở ví dụ thứ hai, không tồn tại một xâu con liên tiếp nào như vậy nên đáp án là "NO".

Ràng buộc

• Subtask \(1\) (\(50\%\) số điểm): \(|s| \lt 255\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.