#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int main ()
{
	int T;
	scanf ("%d", &T);
	while (T --)
	{
		string str;
		cin >> str;
		int n = str.size ();
		bool have_ans = false;
		for (int i = 0; i <= n; i ++)
		{
			bool ok = false;
			for (char ch = 'a'; ch <= 'z'; ch ++)
			{
				bool ak = true;
				string l = "";
				for (int j = 0, k = 0; j <= n; j ++)
					if (j == i)
						l.push_back(ch);
					else
					{
						l.push_back(str[k]);
						k ++;
					}
				for (int j = 0; j < l.size(); j ++)
					if (l[j] != l[n - j])
					{
						ak = false;
						break;
					}
				if (ak)
				{
					cout << l << endl;
					ok = true;
					break;
				}
			}
			if (ok)
			{
				have_ans = true;
				break;
			}
		}
		if (!have_ans)
			puts("NA");
	}
}