#include <bits/stdc++.h>

using namespace std;

int last_dp[3];
int dp[1000010][3];
const int INF = 1e9;
int n;
char s[1000010];

bool ok(char ch) {
  return ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U' ||
         ch == 'Y';
}

int min3(int a, int b, int c) { return min(a, min(b, c)); }

int main() {
  last_dp[0] = 0;
  last_dp[1] = INF;
  last_dp[2] = INF;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    int m = strlen(s + 1);
    for (int j = 1; j <= m + 1; j++) {
      dp[j][0] = dp[j][1] = dp[j][2] = INF;
    }
    dp[0][0] = last_dp[0];
    dp[0][1] = last_dp[1];
    dp[0][2] = last_dp[2];
    last_dp[0] = last_dp[1] = last_dp[2] = INF;
    for (int j = 1; j <= m; j++) {
      int v = ok(s[j]) ? 1 : 0;
      if (v) {
        dp[j][0] =
            min(dp[j][0], min3(dp[j - 1][0], dp[j - 1][1], dp[j - 1][2]) + 1);
      } else {
        for (int k = 1; k <= 2; k++) {
          dp[j][k] = min(dp[j][k], dp[j - 1][k - 1] + 1);
        }
      }
      for (int k = 0; k <= 2; k++) {
        last_dp[k] = min(last_dp[k], dp[j][k]);
      }
    }
    int ans = min3(last_dp[0], last_dp[1], last_dp[2]);
    if (ans > INF / 2) {
      puts("*");
    } else {
      printf("%d\n", ans);
    }
  }
}