Litera

Mai sunt câteva săptămâni și vine vacanța. Ajuns într-un magazin de jucării, Robert îl roagă pe tatăl său să-i cumpere cea mai frumoasă mașină cu telecomandă. Tatăl său îi spune că nu a fost cuminte în timpul anului și nu merită această jucărie, însă după dispute intense acesta hotărăște să-i mai acorde o șansă doar dacă va rezolva urmatoarea problemă: Având un string $S$, putem să obținem un palindrom din acest șir ștergând un singur caracter. Robert nu se prea descurcă la algoritmică așa că vă roagă foarte mult să-i rezolvați problema pentru a se putea juca cu mașina cu telecomandă.

Cerință

Find dat un string $S$, se poate obține un palindrom din șirul inițial ștergând doar un singur caracter.

Date de intrare

Fişierul de intrare litera.in conţine pe prima linie o valoare $T$ reprezentând numărul de teste. Pe următoarele $T$ linii vom avea câte un string reprezentând întrebarea adresată lui Robert de către tatăl său.

Date de ieșire

Fişierul de ieşire litera.out va conține $T$ linii cu răspunsul YES dacă se poate obține un palindrom ștergând un singur caracter și NO dacă nu se poate obține.

Restricții și precizări

• $T ≤ 100$
• Dimensiunea string-ului $\leq 100 \ 000$
• Pentru $10\%$ din punctaj dimensiunea stringului $≤ 1 \ 000$
• String-ul conține caractere de la a la z.
• Dimensiunea string-ului după ștergerea unui caracter va fi mai mică decât a fost înainte.

Exemplul 1

litera.in

4
aaa
abc
abdbca
abba

litera.out

YES
NO
YES
YES

Explicație

• Pentru primul exemplu (aaa): Putem șterge orice a, string-ul rezultat este aa care este palindrom.
• Pentru al II-lea exemplu (abc): Nu este posibil să eliminăm exact un singur caracter și sa obținem un palindrom.
• Pentru al III-lea exemplu (abdbca): Ștergem caracterul c, string-ul rezultat este abdba care este palindrom.
• Pentru exemplul IV (abba): Ștergem b, obținem aba care este palindrom.