Vasilut Lucian (Vasilut) Mai sunt câteva săptămâni și vine Crăciunul. 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 hotaraste să-i mai acorde o sansă, doar dacă va rezolva următoarea problema:
Având un string S, putem să obținem un palindrom din acest șir ștergând un singur caracter?
Robert nu se prea descurca la algoritmică așa că vă roagă foarte mult să-i rezolvați problema pentru a se putea juca cu mașina cu telecomandă. În schimbul acestei mașini el vă va recompensa cu 100 puncte.
Cerința
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 constructpalindrom.in conţine pe prima linie o valoare T reprezentând numărul de teste. Pe următoarele T linii vom avea cate un string reprezentând întrebarea adresata lui Robert de către tatăl sau.
Date de ieșire
Fişierul de ieşire constructpalindrom.out va conține T linii cu răspunsul YES daca se poate obține un palindrom ștergând un singur caracter și NO dacă nu se poate obține.
Restricții și precizări
1 <= T <= 100- Dimensiunea stringului
<= 100000 - Pentru 10% din punctaj dimensiunea stringului
<= 1000 - String-ul conține caractere de la
alaz. - Dimensiunea string-ului după ștergerea unui caracter va fi mai mică decât a fost înainte.
Exemplu:
constructpalindrom.in
4 aaa abc abdbca abba
constructpalindrom.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 doilea exemplu (abc): Nu este posibil să eliminăm exact un caracter și să obtinem un palindrom.
Pentru al treilea exemplu (abdbca): ștergem caracterul c, string-ul rezultat este abdba care este palindrom.
Pentru exemplul al patrulea (abba): Ștergem b, obținem aba care este palindrom.