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 a la z.
• 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.

#include <bits/stdc++.h>

using namespace std;

char s[100001];

ifstream cin("constructpalindrom.in");
ofstream cout("constructpalindrom.out");

int main()
{
    int t;
    cin >> t;
    for(int q = 1 ; q <= t ; ++q)
    {
        cin >> s;
        int n = strlen(s);
        int cnt = 0;
        bool ok = true;
        for(int i = 0 , j = n - 1 ; i < j ; ++i , j--)
            if(s[i]!=s[j])
            {
                j--;
                cnt++;
                if(s[i]!=s[j])
                    j++,i--;
                if(s[i]!=s[j])
                {
                    ok=false;
                    break;
                }
            }
        if(ok == true && cnt <= 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}