There are 2 observstions needed to solve the problem:
Let's define the numbers of vowels by $$$a_0, \cdots, a_4$$$ and assume we have fixed them. Obviously, $$$a_0 + \cdots + a_4 = n$$$.
At first, let's not consider the empty string as it doesn't change anything. Then, the number of palindrome subsequences will be at least $$$A = 2^{a_0} + \cdots + 2^{a_4} - 5$$$ (every subsequence consisting of the same letter minus the 5 empty strings). Now, notice that if we put the same characters consecutively then the answer would be exactly A, and that would be the best possible answer for that fixed numbers (there can't be other palindrome subsequences because if the first and last characters are the same, then all the middle part will be the same as well).
Now, we need to find the best array $$$a$$$. To do this, let's assume there are 2 mumbers $$$x$$$ and $$$y$$$ in the array such that $$$x + 2 \leq y$$$. Then, $$$2^x + 2^y > 2 \cdot 2^{y-1} \geq 2^{x+1} + 2^{y-1}$$$. This means, that replacing $$$x$$$ and $$$y$$$ with $$$x+1$$$ and $$$y-1$$$ will not change the sum of the array $$$a$$$ but will make the number of palindrome subsequences smaller. We can do this replacing process until no two numbers in $$$a$$$ have difference bigger than $$$1$$$. Actually, there is only one such array (not considering its permutations) and it contains only $$$(n$$$ $$$/$$$ $$$5)$$$-s and $$$((n$$$ $$$/$$$ $$$5) + 1)$$$-s.
#include <bits/stdc++.h>
using namespace std;
const string VOWELS = "aeiou";
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; // test cases
while (t--) {
int n; cin >> n; // string length
vector<int> v(5, n / 5); // n - (n % 5) numbers should be (n / 5)
for (int i = 0; i < n % 5; i++) v[i]++; // and the others should be (n / 5) + 1
for (int i = 0; i < 5; i++) for (int j = 0; j < v[i]; j++) cout << VOWELS[i]; // output VOWELS[i] v[i] times
cout << "\n";
}
}
