#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
int dist(char a, char b)
{
if(a>b) swap(a, b);
int d = b - a;
d = min(d, 26 - d);
return d;
}
const int N = 100001;
int dp[N][26];
int mini[N];
char pos[N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--)
{
int k; cin >> k;
ll kk = k;
string s; cin >> s;
string t = s;
int n = int(s.length());
for(int i = 0; i < n; i++)
{
mini[i] = 1000000000;
for(int j = 0; j < 26; j++)
{
if(i != n - 1 - i) dp[i][j] = dist(s[i], char(j+'a')) + dist(s[n-1-i], char(j+'a'));
else dp[i][j] = dist(s[i], char(j+'a'));
if(mini[i] > dp[i][j])
{
mini[i] = dp[i][j];
pos[i] = char(j+'a');
}
}
s[i] = pos[i]; s[n-1-i] = pos[i];
k -= mini[i];
}
if(k < 0)
{
cout << -1 << '\n';
continue;
}
for(int i = 0; i <= n - 1 - i; i++)
{
if(k < 0) break;
for(int j = 0; j < s[i] - 'a'; j++)
{
if(dp[i][j] - mini[i] <= k)
{
k -= (dp[i][j] - mini[i]);
s[i] = s[n-1-i] = char(j+'a');
break;
}
}
}
for(int i = 0; i < n; i++)
{
assert(s[i]==s[n-1-i]);
}
ll d = 0;
for(int i = 0; i < n; i++)
{
d += dist(s[i], t[i]);
}
assert(d<=kk);
cout << s << '\n';
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CiAKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZibyBmaW5kX2J5X29yZGVyCiNkZWZpbmUgb29rIG9yZGVyX29mX2tleQogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7IAp0eXBlZGVmIHRyZWU8aW50LCBudWxsX3R5cGUsIGxlc3M8aW50PiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT4gcGJkczsKdHlwZWRlZiBzZXQ8aW50Pjo6aXRlcmF0b3Igc2l0Owp0eXBlZGVmIG1hcDxpbnQsaW50Pjo6aXRlcmF0b3IgbWl0Owp0eXBlZGVmIHZlY3RvcjxpbnQ+OjppdGVyYXRvciB2aXQ7CgppbnQgZGlzdChjaGFyIGEsIGNoYXIgYikKewoJaWYoYT5iKSBzd2FwKGEsIGIpOwoJaW50IGQgPSBiIC0gYTsKCWQgPSBtaW4oZCwgMjYgLSBkKTsKCXJldHVybiBkOwp9Cgpjb25zdCBpbnQgTiA9IDEwMDAwMTsKaW50IGRwW05dWzI2XTsKaW50IG1pbmlbTl07CmNoYXIgcG9zW05dOwoKaW50IG1haW4oKQp7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKDApOwoJaW50IHQ7IGNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQlpbnQgazsgY2luID4+IGs7CgkJbGwga2sgPSBrOwoJCXN0cmluZyBzOyBjaW4gPj4gczsKCQlzdHJpbmcgdCA9IHM7CgkJaW50IG4gPSBpbnQocy5sZW5ndGgoKSk7CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQl7CgkJCW1pbmlbaV0gPSAxMDAwMDAwMDAwOwoJCQlmb3IoaW50IGogPSAwOyBqIDwgMjY7IGorKykKCQkJewoJCQkJaWYoaSAhPSBuIC0gMSAtIGkpIGRwW2ldW2pdID0gZGlzdChzW2ldLCBjaGFyKGorJ2EnKSkgKyBkaXN0KHNbbi0xLWldLCBjaGFyKGorJ2EnKSk7CgkJCQllbHNlIGRwW2ldW2pdID0gZGlzdChzW2ldLCBjaGFyKGorJ2EnKSk7CgkJCQlpZihtaW5pW2ldID4gZHBbaV1bal0pCgkJCQl7CgkJCQkJbWluaVtpXSA9IGRwW2ldW2pdOwoJCQkJCXBvc1tpXSA9IGNoYXIoaisnYScpOwoJCQkJfQoJCQl9CgkJCXNbaV0gPSBwb3NbaV07IHNbbi0xLWldID0gcG9zW2ldOwoJCQlrIC09IG1pbmlbaV07CgkJfQoJCWlmKGsgPCAwKQoJCXsKCQkJY291dCA8PCAtMSA8PCAnXG4nOwoJCQljb250aW51ZTsKCQl9CgkJZm9yKGludCBpID0gMDsgaSA8PSBuIC0gMSAtIGk7IGkrKykKCQl7CgkJCWlmKGsgPCAwKSBicmVhazsKCQkJZm9yKGludCBqID0gMDsgaiA8IHNbaV0gLSAnYSc7IGorKykKCQkJewoJCQkJaWYoZHBbaV1bal0gLSBtaW5pW2ldIDw9IGspCgkJCQl7CgkJCQkJayAtPSAoZHBbaV1bal0gLSBtaW5pW2ldKTsKCQkJCQlzW2ldID0gc1tuLTEtaV0gPSBjaGFyKGorJ2EnKTsgCgkJCQkJYnJlYWs7CgkJCQl9CgkJCX0KCQl9CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQl7CgkJCWFzc2VydChzW2ldPT1zW24tMS1pXSk7CgkJfQoJCWxsIGQgPSAwOwoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJewoJCQlkICs9IGRpc3Qoc1tpXSwgdFtpXSk7CgkJfQoJCWFzc2VydChkPD1rayk7CgkJY291dCA8PCBzIDw8ICdcbic7Cgl9Cn0K