for _ in range(int(input())):
n = int(input())
s = input()
p1=0
p2=0
cntC=0
cntB=0
ans = float('inf')
if ('abbacca' in s) or ('accabba' in s):
ans = 7
while p1<n:
if s[p1]=='a':
p2=p1+1
break
else:
p1+=1
while p2<n:
if s[p2]=='a':
if cntB<2 and cntC<2:
ans = min(ans,p2-p1+1)
cntB=0
cntC=0
p1=p2
p2+=1
if ans==2:
break
elif s[p2]=='b':
cntB+=1
p2+=1
else:
cntC+=1
p2+=1
if ans>n:
print(-1)
else:
print(ans)#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const char nl = '\n';
const ll INF = 4000000000000000000;
const int MOD = 1000000007; // 998244353
int f(string &s, int l, int r) {
int cnt = 0;
for (int i = l; i <= r; ++i) {
if (s[i] == 'b') {
++cnt;
}
}
return max(cnt, r-l-cnt);
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
for (int i = 0; i+1 < n; ++i) {
if (s[i] == 'a' && s[i+1] == 'a') {
cout << 2 << nl;
return;
}
}
for (int i = 0; i+2 < n; ++i) {
if (s[i] == 'a' && s[i+2] == 'a') {
cout << 3 << nl;
return;
}
}
for (int i = 0; i+3 < n; ++i) {
if (s[i] == 'a' && s[i+3] == 'a' && s[i+1] != s[i+2]) {
cout << 4 << nl;
return;
}
}
for (int i = 0; i + 6 < n; ++i) {
if (s[i] == 'a' && s[i+3] == 'a' && s[i+6] == 'a' && f(s, i+1, i+5) < 3) {
cout << 7 << nl;
return;
}
}
cout << -1 << nl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
}
/* TEMPLATE NOTES
New ideas?
Overflow error?
Array bound?
a*(b/c) != a*b/c
*/
// LEMMA: odgovor pocinje sa A.
// dokaz: Pretpostavimo da ne pocinje sa A.
// Taj string tada pocinje sa B ili sa C.
// Neka Acnt, Bcnt i Ccnt redom oznacavaju
// broj pojavljivanja A, B i C u tom odgovoru.
// Neka su l i r pocetak i kraj polozaja naseg
// odgovora u stringu. String l+1 i r je isto
// tacan jer, ako je Acnt > max(Bcnt, Ccnt),
// Onda je i Acnt vece od oba broja pojavljivanja
// B i C u string l+1 i r. Duzina odgovora koji smo
// prvobitno gledali je r-l, a duzina ovog novog validnog
// string je r-l-1. Kako je r-l-1 < r-l, dobijamo kontradikciju.
// Slicno se i dokazuje da se zavrsava sa A.349A - Cinema Line | 47A - Triangular numbers |
1516B - AGAGA XOOORRR | 1515A - Phoenix and Gold |
1515B - Phoenix and Puzzle | 155A - I_love_username |
49A - Sleuth | 1541A - Pretty Permutations |
1632C - Strange Test | 673A - Bear and Game |
276A - Lunch Rush | 1205A - Almost Equal |
1020B - Badge | 1353A - Most Unstable Array |
770A - New Password | 1646B - Quality vs Quantity |
80A - Panoramix's Prediction | 1354B - Ternary String |
122B - Lucky Substring | 266B - Queue at the School |
1490A - Dense Array | 1650B - DIV + MOD |
1549B - Gregor and the Pawn Game | 553A - Kyoya and Colored Balls |
1364A - XXXXX | 1499B - Binary Removals |
1569C - Jury Meeting | 108A - Palindromic Times |
46A - Ball Game | 114A - Cifera |