#include<bits/stdc++.h>
#include "testlib.h"
using namespace std;
int palindrome(string s)
{
for (int i = 0; i < s.size(); i++)
{
if (s[i] != s[(int) s.size() - i - 1])
return false;
}
return true;
}
int canDoWithSingleDelete(int position, string s)
{
//return false;
string t = "";
for (int i = 0; i < s.size(); i++)
if (i == position)
continue;
else
t += s[i];
return palindrome(t);
}
int valid(int center, string s)
{
// case when we need to delete the center itself.
if (canDoWithSingleDelete(center, s))
return true;
if (canDoWithSingleDelete(0, s))
return true;
if (canDoWithSingleDelete((int) s.size() - 1, s))
return true;
for (int diff1 = 0; diff1 <= 1; diff1++)
for (int diff2 = 0; diff2 <= 1; diff2++)
{
int lptr = center - diff1;
int rptr = center + diff2;
//cout << lptr << " " << rptr << endl;
int lStart = lptr;
int rStart = rptr;
while (lptr >= 0 && rptr < s.size())
{
if (s[lptr] != s[rptr])
{
if (canDoWithSingleDelete(lptr, s)) return true;
if (canDoWithSingleDelete(rptr, s)) return true;
break;
}
lptr--;
rptr++;
}
}
return false;
}
int smartSolve(string s)
{
vector<int> centerCandidate;
for (int i = -2; i <= 2; i++)
{
int idx = s.size() / 2 + i;
if (idx >= 0 && idx < s.size())
centerCandidate.push_back(idx);
}
int ok = false;
for (int ct = 0; ct < centerCandidate.size(); ct++)
{
int center = centerCandidate[ct];
if (valid(center, s))
{
ok = true;
break;
}
}
return ok;
}
int bruteSolve(string s)
{
for (int i = 0; i < s.size(); i++)
{
string t = "";
for (int j = 0; j < s.size(); j++)
{
if (i == j) continue;
t += s[j];
}
if (palindrome(t))
return true;
}
return false;
}
#define BRUTE
vector<string> testStrings;
void rec(int id, string s, int alphaSize, int len)
{
if (id == len)
{
testStrings.push_back(s);
}
else
{
for (char ch = 'a'; ch <= 'a' + alphaSize; ch++)
{
string t = s;
t += ch;
rec(id + 1, t, alphaSize, len);
}
}
}
void check(string s)
{
int ok1 = smartSolve(s);
int ok2 = bruteSolve(s);
if (ok1 != ok2)
{
cout << s << endl;
cout << ok1 << " " << ok2 << endl;
assert(ok1 == ok2);
}
}
#define TEST_GEN
//#define TEST2
void print(char file[], vector<string> a)
{
ofstream out;
out.open(file);
out << a.size() << endl;
cout << a.size() << endl;
for (int i = 0; i < a.size(); i++)
out << a[i] << endl;
out.close();
}
void gen(char file[])
{
int totalLen = 0;
vector<string> strs;
for (int len = 2; len <= 30; len++)
{
for (int mask = 0; mask < (1 << len); mask++)
{
string s = "";
for (int i = 0; i < len; i++)
if (mask & (1 << i))
s += "a";
else s += "b";
if (totalLen + s.size() <= 1000000)
{
totalLen += s.size();
strs.push_back(s);
}
else goto done;
}
}
done:
print(file, strs);
}
void gen1(char file[])
{
int totalLen = 0;
vector<string> strs;
for (int len = 2; len < 10; len++)
{
testStrings.clear();
rec(0, "", 3, len);
for (int i = 0; i < testStrings.size(); i++)
{
string s = testStrings[i];
if (totalLen + s.size() <= 1000000)
{
totalLen += s.size();
strs.push_back(s);
}
else goto done;
}
}
done:
print(file, strs);
}
void gen2(char file[])
{
int totalLen = 0;
vector<string> strs;
for (int len = 2; len < 10; len++)
{
testStrings.clear();
rec(0, "", len, len);
for (int i = 0; i < testStrings.size(); i++)
{
string s = testStrings[i];
if (totalLen + s.size() <= 1000000)
{
totalLen += s.size();
strs.push_back(s);
}
else goto done;
}
}
done:
print(file, strs);
}
string createRandomPalin(int len)
{
string s = "";
for (int i = 0; i < len / 2; i++)
s += (char) ('a' + rnd.next(0, 25));
string t = s;
reverse(t.begin(), t.end());
if (len % 2 == 0)
return s + t;
else
{
string ans = s;
ans += (char) ('a' + rnd.next(0, 25));
ans += t;
return ans;
}
}
string change(string s, int place)
{
string t = "";
for (int i = 0; i < place; i++)
t += s[i];
t += (char) ('a' + rnd.next(0, 25));
for (int i = place; i < s.size(); i++)
t += s[i];
return t;
}
void gen3(char file[])
{
int totalLen = 0;
vector<string> strs;
for (int tc = 0; tc < 10000; tc++)
{
int len = rnd.next(2, 1000);
string s = createRandomPalin(len);
int place = rnd.next(0, len - 1);
s = change(s, place);
if (totalLen + s.size() <= 1000000)
{
if (rnd.next(1, 2) == 2)
{
int place = rnd.next(0, (int)s.size() - 1);
s[place] = (char) ('a' + rnd.next(0, 25));
}
totalLen += s.size();
strs.push_back(s);
}
else goto done;
}
done:
print(file, strs);
}
void gen4(char file[])
{
int totalLen = 0;
vector<string> strs;
for (int tc = 0; tc < 10; tc++)
{
int len = 99999;
string s = createRandomPalin(len);
int place = rnd.next(0, len - 1);
s = change(s, place);
if (totalLen + s.size() <= 1000000)
{
if (rnd.next(1, 2) == 2)
{
int place = rnd.next(0, (int)s.size() - 1);
s[place] = (char) ('a' + rnd.next(0, 25));
}
totalLen += s.size();
strs.push_back(s);
}
else goto done;
}
done:
print(file, strs);
}
void gen5(char file[])
{
int totalLen = 0;
vector<string> strs;
for (int tc = 0; tc < 10; tc++)
{
int len = 99999;
string s = createRandomPalin(len);
int place = rnd.next(0, len - 1);
s = change(s, place);
if (totalLen + s.size() <= 1000000)
{
if (rnd.next(1, 2) == 2)
{
for (int ct = 0; ct < rnd.next(1, 10); ct++)
{
int place = rnd.next(0, (int)s.size() - 1);
s[place] = (char) ('a' + rnd.next(0, 25));
}
}
totalLen += s.size();
strs.push_back(s);
}
else goto done;
}
done:
print(file, strs);
}
int main(int argc, char *argv[])
{
registerGen(argc, argv);
#ifdef BRUTE
#ifdef TEST1
for (int len = 2; len <= 15; len++)
{
for (int mask = 0; mask < (1 << len); mask++)
{
string s = "";
for (int i = 0; i < len; i++)
if (mask & (1 << i))
s += "a";
else s += "b";
int ok1 = smartSolve(s);
int ok2 = bruteSolve(s);
if (ok1 != ok2)
{
cout << s << endl;
cout << ok1 << " " << ok2 << endl;
assert(ok1 == ok2);
}
}
}
#endif // TEST1
#ifdef TEST2
int total = 0;
for (int len = 2; len < 10; len++)
{
testStrings.clear();
rec(0, "", len);
for (int i = 0; i < testStrings.size(); i++)
{
//cout << testStrings[i] << endl;
check(testStrings[i]);
total += testStrings[i].size();
}
}
cout << total << endl;
#endif // TEST1
#else
int T;
cin >> T;
assert(T >= 1 && T <= 1000000);
while (T--)
{
string s;
cin >> s;
assert(s.size() >= 2 && s.size() <= 100000);
if (smartSolve(s)) cout << "YES" << endl;
else cout << "NO" << endl;
}
#endif // BRUTE
#ifdef TEST_GEN
gen("1.in");
gen1("2.in");
gen2("3.in");
gen3("4.in");
gen4("5.in");
gen5("6.in");
#endif // TEST_GEN
return 0;
}
// babbbbbb