#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, infl)));
		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] != infl)
				return dp[i][x][curr];
			dp[i][x][curr] = inf;
			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';
                return;
	}
	{
	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" : "");
	}
}