#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <climits>
#include <cmath>
#include <numeric>
#include <string>
#include <bitset>
#include <assert.h>
#include <iomanip>
using namespace std;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
/*
#include <bits/stdc++.h>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)
*/
const long long infl = 1e18 + 1;
const int inf = 1e9 + 1;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const long double eps = 1e-7;
const int mod = mod1;
int add(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }
int mul(int a, int b) { return (int)((long long)a * b % mod); }
int pwr(int a, int b = mod - 2)
{
int res = 1;
for(; b > 0; b >>= 1, a = mul(a, a))
if(b & 1)
res = mul(res, a);
return res;
}
template <typename T>
bool chmax(T &a, T b)
{
if(b > a)
{
a = b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, T b)
{
if(b < a)
{
a = b;
return true;
}
return false;
}
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
string t = "aeiou";
{
vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(5, vector<long long>(32, inf)));
auto tt = [&](char c) -> int
{
return find(t.begin(), t.end(), c) - t.begin();
};
auto rec = [&](auto self, int i, char lst, int curr) -> long long
{
if(i == n)
return 0;
int x = tt(lst);
if(dp[i][x][curr] != inf)
return dp[i][x][curr];
int y = tt(s[i]);
if((curr >> y) & 1)
{
if(y == x)
chmin(dp[i][x][curr], self(self, i + 1, s[i], curr));
char z = t[(y + 1) % 5];
int cnt = 1;
while(z != s[i])
{
int xx = tt(z);
if(xx == x)
{
chmin(dp[i][x][curr], cnt + self(self, i + 1, lst, curr));
}
if((curr >> xx) & 1)
{
z = t[(xx + 1) % 5];
cnt++;
continue;
}
chmin(dp[i][x][curr], cnt + self(self, i + 1, z, curr | (1 << xx)));
z = t[(xx + 1) % 5];
cnt++;
}
}
else
{
chmin(dp[i][x][curr], self(self, i + 1, s[i], curr | (1 << y)));
char z = t[(y + 1) % 5];
int cnt = 1;
while(z != s[i])
{
int xx = tt(z);
if(xx == x)
{
chmin(dp[i][x][curr], cnt + self(self, i + 1, lst, curr));
}
if((curr >> xx) & 1)
{
z = t[(xx + 1) % 5];
cnt++;
continue;
}
chmin(dp[i][x][curr], cnt + self(self, i + 1, z, curr | (1 << xx)));
z = t[(xx + 1) % 5];
cnt++;
}
}
return dp[i][x][curr];
};
cout << rec(rec, 0, s[0], 0);// << '\n';
}
{
vector dp(n, vector<long long>(5, inf));
auto tt = [&](char c) -> int
{
return find(t.begin(), t.end(), c) - t.begin();
};
auto rec = [&](auto self, int i, char lst, vector<bool> curr) -> long long
{
if(i == n)
return 0;
if(dp[i][tt(lst)] != inf)
return dp[i][tt(lst)];
if(curr[tt(s[i])] == true)
{
if(s[i] == lst)
dp[i][tt(lst)] = min(dp[i][tt(lst)], self(self, i + 1, lst, curr));
char c = t[(tt(s[i]) + 1) % 5];
int cnt = 1;
while(c != s[i])
{
if(c == lst)
{
dp[i][tt(lst)] = min(dp[i][tt(lst)], cnt + self(self, i + 1, lst, curr));
}
if(curr[tt(c)] == true)
{
c = t[(tt(c) + 1) % 5];
cnt++;
continue;
}
curr[tt(c)] = true;
dp[i][tt(lst)] = min(dp[i][tt(lst)], cnt + self(self, i + 1, c, curr));
curr[tt(c)] = false;
cnt++;
c = t[(tt(c) + 1) % 5];
}
}
else
{
curr[tt(s[i])] = true;
dp[i][tt(lst)] = min(dp[i][tt(lst)], self(self, i + 1, s[i], curr));
char c = t[(tt(s[i]) + 1) % 5];
int cnt = 1;
while(c != s[i])
{
if(curr[tt(c)] == true)
{
c = t[(tt(c) + 1) % 5];
cnt++;
continue;
}
curr[tt(c)] = true;
dp[i][tt(lst)] = min(dp[i][tt(lst)], cnt + self(self, i + 1, c, curr));
curr[tt(c)] = false;
cnt++;
c = t[(tt(c) + 1) % 5];
}
curr[tt(s[i])] = false;
}
return dp[i][tt(lst)];
};
// cout << rec(rec, 0, s[0], vector<bool>(5, false));
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
cout << (t ? "\n" : "");
}
}