Utkarsh has recently started taking English-language classes to improve his reading and writing skills. However, he is still struggling to learn English. His teacher gave him the following problem to improve his vowel-identification skills:

There is a string S of length N consisting of lowercase English letters only. Utkarsh has to start from the first letter of the string.  
Each time he encounters a vowel (i.e. a character from the set \{a, e, i, o, u\}) he has to reverse the entire substring that came before the vowel. 

Utkarsh needs help verifying his answer. Can you print the final string after performing all the operations for him? 

------ Input Format ------ 

- First line will contain T, number of test cases. Then T test cases follow.
- The first line of each test case contains N, the length of the string.
- The second line contains S, the string itself.

------ Output Format ------ 

For each test case, output in a single line the final string after traversing S from left to right and performing the necessary reversals.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
10
abcdefghij
7
bcadage
----- Sample Output 1 ------ 
hgfeabcdij
gacbade
----- explanation 1 ------ 
Test case $1$: The first letter is a vowel, but there is no substring before it to reverse, so we leave it as it is. Next, we reverse abcd and the string becomes dcbaefghij. Next we reach the vowel i and reverse dcbaefgh to get the string hgfeabcdij.

Test case $2$: Initially, we reverse bc and the string becomes cbadage. Next we reach the vowel a and reverse cbad to get the string dabcage. Finally we reach the vowel e and reverse dabcag to get the string gacbade.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Amortized analysis


Solutions:
from collections import deque
for i in range(int(input())):
	input()
	s = input()
	pi = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
	v = []
	for i in range(len(s)):
		if s[i] in pi:
			v.append(i + 1)
	reverse = ''
	current = ''
	p = deque()
	flag = 0
	for i in range(len(s)):
		if s[i] in pi:
			flag = abs(flag - 1)
			if flag == 0:
				p.appendleft(s[i])
			else:
				p.append(s[i])
		elif flag == 0:
			p.appendleft(s[i])
		else:
			p.append(s[i])
	if flag == 0:
		while True:
			if len(p) == 0:
				break
			current += p.pop()
	else:
		while True:
			if len(p) == 0:
				break
			current += p.popleft()
	print(current)


from collections import deque
t = int(input())
vowels = {'a', 'e', 'i', 'o', 'u'}
for _ in range(t):
	n = int(input())
	s = str(input())
	cur = deque()
	rev = deque()
	for i in s:
		if i in vowels:
			temp = cur
			cur = rev
			rev = temp
			cur.append(i)
			rev.appendleft(i)
		else:
			cur.append(i)
			rev.appendleft(i)
	print(''.join(list(cur)))


for i in range(int(input())):
	n = int(input())
	string = input()
	s = [0 for i in range(n)]
	(l, r) = (0, n - 1)
	c = 0
	vowels = ['a', 'e', 'i', 'o', 'u']
	for i in reversed(range(n)):
		if c % 2 == 0:
			s[r] = string[i]
			r -= 1
		else:
			s[l] = string[i]
			l += 1
		if string[i] in vowels:
			c += 1
	print(''.join(s))


for _ in range(int(input())):
	n = int(input())
	s = [*input()]
	q = []
	prev = 0
	vowel = {*'aeiou'}
	for i in range(n):
		if s[i] in vowel:
			q.append((prev, i))
			prev = i
	if q:
		last = q[-1][1]
		ans = []
		for i in range(len(q) - 1, -1, -2):
			(x, y) = q[i]
			ans += s[x:y][::-1]
		for i in range(len(q) & 1, len(q), 2):
			(x, y) = q[i]
			ans += s[x:y]
		print(''.join(ans + s[last:]))
	else:
		print(''.join(s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	vowels = ['a', 'e', 'i', 'o', 'u']
	a = ['0'] * n
	l = 0
	r = n - 1
	deal = False
	for i in range(n - 1, -1, -1):
		if deal:
			a[l] = s[i]
			l += 1
		else:
			a[r] = s[i]
			r -= 1
		if s[i] in vowels:
			deal = not deal
	print(''.join(a))


for i in range(int(input())):
	n = int(input())
	s = input()
	b = [0 for i in range(n)]
	right = n - 1
	left = 0
	vowelc = 0
	vowels = ['a', 'e', 'i', 'o', 'u']
	for i in reversed(range(n)):
		if vowelc % 2 == 0:
			b[right] = s[i]
			right -= 1
		else:
			b[left] = s[i]
			left += 1
		if s[i] in vowels:
			vowelc += 1
	print(''.join(b))


vo = 'aeiou'
for _ in range(int(input())):
	n = int(input())
	s = input()
	res = ['0'] * n
	(l, r) = (0, n - 1)
	flag = False
	for i in range(n - 1, -1, -1):
		if flag:
			res[l] = s[i]
			l += 1
		else:
			res[r] = s[i]
			r -= 1
		if s[i] in vo:
			flag = not flag
	print(''.join(res))


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	l = 0
	r = n - 1
	lisst = [0] * n
	rev = False
	for i in range(n - 1, -1, -1):
		if rev:
			lisst[l] = s[i]
			l += 1
		else:
			lisst[r] = s[i]
			r -= 1
		if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			rev = not rev
	print(''.join(lisst))


for _ in range(int(input())):
	n = int(input())
	string = input()
	vowels = ['a', 'e', 'i', 'o', 'u']
	ans = ['0'] * n
	op = False
	right = 0
	left = n - 1
	for i in reversed(range(n)):
		if op:
			ans[right] = string[i]
			right += 1
		else:
			ans[left] = string[i]
			left -= 1
		if string[i] in vowels:
			op = not op
	print(''.join(ans))


for t in range(int(input())):
	n = int(input())
	s = input()
	v = ['a', 'e', 'i', 'o', 'u']
	t1 = ''
	t2 = ''
	c = 0
	s = s[::-1]
	for i in s:
		if c % 2:
			t1 += i
		else:
			t2 += i
		if i in v:
			c += 1
	print(t1 + t2[::-1])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = ['a', 'e', 'i', 'o', 'u']
	a = []
	temp = ''
	cnt = 0
	for i in range(len(s)):
		if i != 0 and s[i] in l:
			a.append(temp)
			temp = ''
			cnt += 1
		temp += s[i]
	ans = []
	if cnt % 2 == 0:
		i = 0
		while i < cnt:
			if i % 2 == 0:
				ans.append(a[i])
			else:
				ans.insert(0, a[i])
			i += 1
	else:
		i = 0
		while i < cnt:
			if i % 2:
				ans.append(a[i])
			else:
				ans.insert(0, a[i])
			i += 1
	ans.append(temp)
	for k in range(cnt // 2 + cnt % 2):
		l = ans[k]
		ans[k] = l[::-1]
	for h in ans:
		print(h, end='')
	print()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	res = deque()
	vowel_count = 0
	for char in s:
		if char in 'aeiou':
			vowel_count += 1
		if vowel_count % 2 == 1:
			res.appendleft(char)
		else:
			res.append(char)
	if vowel_count % 2 == 1:
		res.reverse()
	for char in res:
		print(char, end='')
	print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	rev = 0
	x = ''
	y = ''
	vow = ['a', 'e', 'i', 'o', 'u']
	for i in range(n - 1, -1, -1):
		if rev:
			y += s[i]
		else:
			x += s[i]
		if s[i] in vow:
			rev = 1 - rev
	y = y[::-1]
	s = (x + y)[::-1]
	print(s)


for _ in range(int(input())):
	n = int(input())
	s = input()
	from collections import deque
	d = deque()
	rev = 0
	x = ''
	y = ''
	vow = ['a', 'e', 'i', 'o', 'u']
	for i in range(n - 1, -1, -1):
		if rev:
			y += s[i]
		else:
			x += s[i]
		if s[i] in vow:
			rev = 1 - rev
	y = y[::-1]
	s = (x + y)[::-1]
	print(s)


T = int(input())
for vinay in range(T):
	N = int(input())
	S = input()
	count = 0
	ans1 = ''
	ans2 = ''
	for c in range(N - 1, -1, -1):
		if count % 2 == 0:
			ans2 = S[c] + ans2
		else:
			ans1 += S[c]
		if S[c] == 'a' or S[c] == 'e' or S[c] == 'i' or (S[c] == 'o') or (S[c] == 'u'):
			count += 1
	print(ans1 + ans2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	arr = [0]
	for i in range(1, n):
		if s[i] in ['a', 'e', 'i', 'o', 'u']:
			arr.append(i)
	l = len(arr)
	count = 1
	temp = []
	ans = ''
	for i in range(l - 1, 0, -1):
		if count % 2 == 0:
			temp.append(s[arr[i - 1]:arr[i]])
		else:
			temp2 = s[arr[i - 1]:arr[i]]
			temp2 = temp2[::-1]
			temp.append(temp2)
		count += 1
	l = l - 1
	flag = 1
	if l % 2 == 0:
		for i in range(l - 1, -1, -1):
			if flag == 1:
				ans = ans + temp[i]
				flag = 0
			else:
				ans = temp[i] + ans
				flag = 1
	else:
		for i in range(l - 1, -1, -1):
			if flag == 1:
				ans = temp[i] + ans
				flag = 0
			else:
				ans = ans + temp[i]
				flag = 1
	ans = ans + s[arr[l]:]
	print(ans)


from collections import deque
for _ in range(int(input())):
	N = int(input())
	S = str(input())
	vowels = 'aeiou'
	count = 0
	de = deque()
	for i in S:
		if i in vowels:
			count = count + 1
			if count % 2 == 0:
				de.append(i)
			else:
				de.appendleft(i)
		elif count % 2 == 0:
			de.append(i)
		else:
			de.appendleft(i)
	for i in range(len(de)):
		if count % 2 == 1:
			a = de.pop()
			print(a, end='')
		else:
			a = de.popleft()
			print(a, end='')
	print('')


from collections import deque

class MyDeque:

	def __init__(self):
		self.queue = deque()
		self.point = 1
		self.appendF = [self.queue.appendleft, self.queue.append]

	def reverse(self):
		self.point ^= 1

	def append(self, el):
		self.appendF[self.point](el)

	def __str__(self):
		if not self.point:
			self.queue.reverse()
		return ''.join(self.queue)
for case in range(int(input())):
	n = int(input())
	S = input()
	myDeque = MyDeque()
	for el in S:
		if el in 'aeiou':
			myDeque.reverse()
		myDeque.append(el)
	print(myDeque)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	ans1 = ''
	ans2 = ''
	count = 0
	for i in range(n - 1, -1, -1):
		if count % 2 == 0:
			ans2 = s[i] + ans2
		else:
			ans1 += s[i]
		if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			count += 1
	print(ans1 + ans2)
	t -= 1


strng = lambda : input().split()[0]
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
slst = lambda : list(input().split()[0])
silst = lambda : list(map(int, input().split()[0]))
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	n = inp()
	s = set(['a', 'e', 'i', 'o', 'u'])
	ans = ''
	a = slst()
	flag = True
	ansrev = ''
	for i in range(n):
		if a[i] in s:
			flag ^= 1
		if flag:
			ans += a[i]
		else:
			ansrev += a[i]
	ans = ansrev[::-1] + ans
	if flag:
		print(ans)
	else:
		print(ans[::-1])


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(ans, temp) = ('', '')
	vowel = ['a', 'e', 'i', 'o', 'u']
	for i in range(n - 1, -1, -1):
		temp = s[i] + temp
		if s[i] in vowel:
			break
	i -= 1
	flag = True
	while i >= 0:
		if flag:
			ans = ans + s[i]
		if s[i] in vowel:
			flag = not flag
		i -= 1
	count = 0
	for i in range(n):
		if s[i] in vowel:
			count += 1
	if count % 2:
		flag = False
	else:
		flag = True
	i = 0
	while i < n:
		if s[i] in vowel:
			flag = not flag
		if flag:
			ans = ans + s[i]
		i += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = input()
	l = list(a)
	ans = ['' for _ in range(n)]
	d = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
	now = n - 1
	y = n - 1
	x = 0
	left = True
	for i in reversed(range(n)):
		if l[i] not in d:
			ans[now] = l[i]
			if left == True:
				now -= 1
			else:
				now += 1
		else:
			ans[now] = l[i]
			if left == True:
				left = False
				now -= 1
				y = now
				now = x
			else:
				left = True
				now += 1
				x = now
				now = y
	print(''.join(ans))


def solve():
	n = int(input())
	s = input()
	vow = ['a', 'e', 'i', 'o', 'u']
	vow_cnt = 0
	res = ''
	data = [-1] * n
	for i in range(n - 1, -1, -1):
		if vow_cnt & 1:
			res += s[i]
		if s[i] in vow:
			data[i] = vow_cnt
			vow_cnt += 1
		else:
			data[i] = vow_cnt
	for i in range(n):
		if not data[i] & 1:
			res += s[i]
	print(res)
for _ in range(int(input())):
	solve()


def solve(n, s):
	first = -1
	vowels = {'a', 'e', 'i', 'o', 'u'}
	for i in range(n - 2, -1, -1):
		if s[i + 1] in vowels:
			first = i
			break
	if first == -1:
		return s
	res = [''] * (first + 1)
	flag = False
	l = 0
	r = first
	for i in range(first, -1, -1):
		if s[i + 1] in vowels:
			flag = not flag
		if flag:
			res[l] = s[i]
			l += 1
		else:
			res[r] = s[i]
			r -= 1
	return ''.join(res) + s[first + 1:]
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


from collections import deque
t = int(input())
for cnt in range(t):
	n = int(input())
	st = list(map(str, input()))
	cnt = 0
	lst = []
	q = deque([])
	for i in range(n):
		if st[i] == 'a' or st[i] == 'e' or st[i] == 'i' or (st[i] == 'o') or (st[i] == 'u'):
			cnt = cnt + 1
		if cnt % 2 == 1:
			q.appendleft(st[i])
		else:
			q.append(st[i])
	for i in range(n):
		if cnt % 2 == 0:
			x = q.popleft()
			print(x, end='')
		else:
			x = q.pop()
			print(x, end='')
	print()


vowels = ['a', 'e', 'i', 'o', 'u']
for _ in range(int(input())):
	N = int(input())
	s = '0' + input()
	A = []
	L = 1
	for i in range(1, N + 1):
		if s[i] in vowels:
			A.append((L, i - 1))
			L = i
	for i in range(len(A) - 1, -1, -2):
		(x, y) = A[i]
		print(s[y:x - 1:-1], end='')
	for i in range(len(A) & 1, len(A), 2):
		(x, y) = A[i]
		print(s[x:y + 1], end='')
	print(s[L:N + 1])


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()[::-1]
	left = []
	right = []
	back = True
	for c in s:
		if back:
			right.append(c)
		else:
			left.append(c)
		if c in 'aeuio':
			back = not back
	right.reverse()
	print(''.join(left + right))


import math

def solve():
	n = int(input())
	s = input()
	r = [0] * n
	c = d = 0
	l = ['a', 'e', 'i', 'o', 'u']
	for i in range(n - 1, -1, -1):
		if d % 2 == 1:
			r[c - 1 - i] = s[i]
		else:
			r[c + i] = s[i]
		if s[i] in l:
			if d % 2 == 1:
				c -= i
			else:
				c += i
			d += 1
	for i in range(n):
		print(r[i], end='')
	print()
T = int(input())
for t in range(T):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	(t, v) = ([''] * n, 0)
	(l, r) = (0, n - 1)
	for i in range(n - 1, -1, -1):
		if v % 2 == 0:
			t[r] = s[i]
			r -= 1
		else:
			t[l] = s[i]
			l += 1
		if s[i] in 'aeiou':
			v += 1
	print(''.join(t))


for _ in range(int(input())):
	n = int(input())
	s = input()
	vowels = ['a', 'e', 'i', 'o', 'u']
	(t, v) = ([''] * n, 0)
	(l, r) = (0, n - 1)
	for i in range(n - 1, -1, -1):
		if v % 2 == 0:
			t[r] = s[i]
			r -= 1
		else:
			t[l] = s[i]
			l += 1
		if s[i] in vowels:
			v += 1
	print(''.join(t))


for i in range(int(input())):
	n = int(input())
	s = input()
	strt = False
	res = [0] * n
	l = 0
	r = n - 1
	for i in range(n - 1, -1, -1):
		if strt:
			res[l] = s[i]
			l += 1
		else:
			res[r] = s[i]
			r -= 1
		if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			strt = ~strt
	for i in range(n):
		print(res[i], end='')
	print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = [0] * n
	p = [0] * n
	c = 0
	for i in s:
		if i in 'aeiou':
			c += 1
	for i in range(n):
		if s[i] in 'aeiou':
			c -= 1
		l[i] = c % 2
	news = ''
	for i in range(n - 1, -1, -1):
		if l[i] % 2 == 1:
			news += s[i]
	for i in range(n):
		if l[i] % 2 == 0:
			news += s[i]
	print(news)


mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter

def main():
	(s, e) = ('', '')
	j = n - 1
	for i in range(n - 1, -1, -1):
		if string[i] in v:
			j = i
			break
		e = string[i] + e
	else:
		print(e)
		return
	k = 0
	flag = True
	while j > -1:
		if string[j] in v and flag:
			e = string[j] + e
			flag = not flag
			j -= 1
			continue
		elif string[j] in v and (not flag):
			s = s + string[j]
			flag = not flag
			j -= 1
			continue
		if not flag:
			s = s + string[j]
			j -= 1
		else:
			e = string[j] + e
			j -= 1
	print(s + e)
t = int(input())
for _ in range(t):
	n = int(input())
	string = input().strip()
	v = {'a', 'e', 'i', 'o', 'u'}
	main()


for _ in range(0, int(input())):
	n = int(input())
	s = input()
	ans = [' '] * n
	vowel = 0
	(left, right) = (0, n - 1)
	for i in range(n - 1, -1, -1):
		if vowel & 1 == 1:
			ans[left] = s[i]
			left += 1
		else:
			ans[right] = s[i]
			right -= 1
		vowel += 1 if s[i] in ['a', 'e', 'i', 'o', 'u'] else 0
	print(''.join((x for x in ans)))


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	q = deque()
	cnt = 0
	for i in range(n):
		if s[i] in ['a', 'e', 'i', 'o', 'u']:
			cnt += 1
		if cnt % 2 == 0:
			q.appendleft(s[i])
		else:
			q.append(s[i])
	if cnt % 2 == 0:
		while len(q) > 0:
			ele = q.pop()
			print(ele, end='')
		print()
	else:
		while len(q) > 0:
			ele = q.popleft()
			print(ele, end='')
		print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	new = []
	l = []
	v = {'a', 'e', 'i', 'o', 'u'}
	for i in range(len(s)):
		if s[i] in v:
			if len(new) != 0:
				new = ''.join(new)
				l.append(new)
			new = [s[i]]
		else:
			new.append(s[i])
	sol = []
	j = len(l) - 1
	i = 0
	first = []
	second = []
	chance = 1
	for x in l[::-1]:
		if chance == 1:
			first.append(x[::-1])
			chance = 2
		else:
			second.insert(0, x)
			chance = 1
	sol = first + second
	new = ''.join(new)
	sol.append(new)
	sol = ''.join(sol)
	print(sol)


for _ in range(int(input())):
	n = int(input())
	s = input()
	s = s[::-1]
	dic = {}
	vowels = ['a', 'e', 'i', 'o', 'u']
	count = 0
	l = 0
	panku = []
	for i in range(n):
		if s[i] in vowels:
			panku.append((s[l:i + 1], count))
			l = i + 1
			count += 1
	if s[l:i + 1] != []:
		panku.append((s[l:i + 1], count))
	o = ''
	e = ''
	panku.sort(key=lambda x: x[1])
	for i in range(len(panku)):
		if panku[i][1] % 2 == 0:
			e = panku[i][0][::-1] + e
		else:
			o = o + panku[i][0]
	print(o + e)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	s = input()
	deq = deque()
	v = 0
	for i in range(n):
		if s[i] in 'aeiou':
			v += 1
		if v & 1:
			deq.appendleft(s[i])
		else:
			deq.append(s[i])
	if v & 1:
		print(''.join(reversed(deq)))
	else:
		print(''.join(deq))


import collections
for _ in range(int(input())):
	n = int(input())
	s = input()
	q = collections.deque()
	v = ['a', 'e', 'i', 'o', 'u']
	front = True
	for i in s:
		if i in v and len(q) > 1:
			front = not front
		if front:
			q.append(i)
		else:
			q.appendleft(i)
	if front:
		ans = ''.join(q)
	else:
		q = list(q)
		ans = ''.join(q[::-1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	flip = 0
	(l, r) = ('', '')
	for i in range(n - 1, -1, -1):
		if flip % 2 == 0:
			r += s[i]
		else:
			l += s[i]
		if s[i] in 'aeiou':
			flip += 1
	print(l + r[::-1])


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	s = input().strip('\n')
	flip = 0
	(l, r) = ('', '')
	for i in range(n - 1, -1, -1):
		if flip % 2 == 0:
			r += s[i]
		else:
			l += s[i]
		if s[i] in 'aeiou':
			flip += 1
	return l + r[::-1]
for _ in range(int(input())):
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ind = [0] * n
	for j in range(n):
		if s[j] in 'aeiou':
			ind[j] -= 1
			ind[0] += 1
	for j in range(1, n):
		ind[j] += ind[j - 1]
	o = [''] * n
	e = n - 1
	st = 0
	for j in range(n - 1, -1, -1):
		if ind[j] % 2 == 0:
			o[e] = s[j]
			e -= 1
		else:
			o[st] = s[j]
			st += 1
	o = ''.join(o)
	print(o)


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	B = [''] * N
	(l, r) = (0, N - 1)
	val = 1
	for i in range(N - 1, -1, -1):
		if val:
			B[r] = A[i]
			r -= 1
		else:
			B[l] = A[i]
			l += 1
		if A[i] == 'a' or A[i] == 'e' or A[i] == 'i' or (A[i] == 'o') or (A[i] == 'u'):
			val = 1 - val
	print(*B, sep='')


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	f = deque([])
	vc = 0
	vow = set(list('aeiou'))
	for i in s:
		if i in vow:
			vc += 1
		if vc & 1:
			f.appendleft(i)
		else:
			f.append(i)
	if vc & 1:
		f.reverse()
		print(''.join(list(f)))
	else:
		print(''.join(list(f)))


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = [''] * n
	k = 0
	j = n - 1
	v = 0
	for i in range(n - 1, -1, -1):
		if v % 2:
			ans[k] = s[i]
			k += 1
		else:
			ans[j] = s[i]
			j -= 1
		if s[i] in 'aeiou':
			v += 1
	print(''.join(ans))


kt = int(input())
while kt:
	p = int(input())
	s = input()
	ans = []
	for i in s:
		ans.append(i)
	h = p - 1
	while h >= 0 and s[h] not in ['a', 'e', 'i', 'o', 'u']:
		h -= 1
	h -= 1
	st = 0
	end = h
	dirl = 0
	ind = h
	while ind >= 0:
		temp = []
		while ind >= 0:
			if s[ind] in ['a', 'e', 'i', 'o', 'u']:
				temp.append(s[ind])
				ind -= 1
				break
			else:
				temp.append(s[ind])
			ind -= 1
		if dirl % 2 == 1:
			for it in temp:
				ans[end] = it
				end -= 1
		else:
			for it in temp:
				ans[st] = it
				st += 1
		dirl += 1
	print(''.join((i for i in ans)))
	kt -= 1


import math
import collections
for _ in range(int(input())):
	N = int(input())
	A = input()
	B = ''
	C = ''
	val = 1
	for i in range(N - 1, -1, -1):
		if A[i] == 'a' or A[i] == 'e' or A[i] == 'i' or (A[i] == 'o') or (A[i] == 'u'):
			if val:
				B += A[i]
			else:
				C += A[i]
			val = 1 - val
		elif val:
			B += A[i]
		else:
			C += A[i]
	B = B[::-1]
	print(C + B)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	k = 1
	p = ''
	q = ''
	for i in range(n - 1, -1, -1):
		if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			if k == 1:
				q += s[i]
			else:
				p += s[i]
			k = 1 - k
		elif k == 1:
			q += s[i]
		else:
			p += s[i]
	q = q[::-1]
	s = p + q
	print(s)


def vowel(s):
	if s == 'a' or s == 'e' or s == 'i' or (s == 'o') or (s == 'u'):
		return True
	else:
		return False
for p in range(int(input())):
	n = int(input())
	a = str(input())
	a = a[::-1]
	(s, q) = ('', '')
	x = 0
	for i in range(n):
		if not vowel(a[i]) and x % 2 == 0:
			s += a[i]
		elif not vowel(a[i]) and x % 2:
			q += a[i]
		elif vowel(a[i]) and x % 2 == 0:
			s += a[i]
			x += 1
		elif vowel(a[i]) and x % 2:
			q += a[i]
			x += 1
	print(q + s[::-1])


def check(s):
	lst = ['a', 'e', 'i', 'o', 'u']
	if s in lst:
		return True
	return False
case = int(input())
mod = 1000000000.0 + 7
for z in range(case):
	n = int(input())
	s = list(input())
	ans = ['-1'] * n
	for i in range(n):
		ans[i] = s[i]
	j = n - 1
	while j >= 0 and (not check(s[j])):
		j -= 1
	j -= 1
	st = 0
	end = j
	dirx = 0
	indx = j
	while indx >= 0:
		tmp = []
		while indx >= 0:
			if check(s[indx]):
				tmp.append(s[indx])
				indx -= 1
				break
			else:
				tmp.append(s[indx])
			indx -= 1
		if dirx % 2 == 1:
			for i in tmp:
				ans[end] = i
				end -= 1
		else:
			for i in tmp:
				ans[st] = i
				st += 1
		dirx += 1
	soln = ''.join(ans)
	print(soln)


for _ in range(int(input())):
	N = int(input())
	S = input()
	A = [0] * len(S)
	direction = -1
	front = 0
	back = len(S) - 1
	S_ = list(S)
	S_.reverse()
	for val in S_:
		if direction == -1:
			A[back] = val
			back -= 1
		else:
			A[front] = val
			front += 1
		if val in 'aeiou':
			direction = -direction
	print(''.join(A))


def is_vowel(ch):
	return ch in 'aeiou'
for _ in range(int(input())):
	n = int(input())
	s = input()
	rev = []
	for i in range(n - 1, -1, -1):
		if is_vowel(s[i]):
			rev.append(i)
	if len(rev) == 0:
		print(s)
		continue
	if rev[-1] != 0:
		rev.append(0)
	end = s[rev[0]:]
	even = ''
	odd = ''
	for i in range(len(rev) - 1):
		while rev[i] - 1 >= rev[i + 1]:
			if i % 2:
				even += s[rev[i] - 1]
			else:
				odd += s[rev[i] - 1]
			rev[i] -= 1
	print(odd + even[::-1] + end)


def reverse_per_vowel(s):
	vowels = {'a', 'e', 'i', 'o', 'u'}
	endings = [[], []]
	side = 1
	for c in reversed(s):
		if c in vowels:
			endings[side].append(c)
			side = 1 - side
		else:
			endings[side].append(c)
	return ''.join(endings[0] + endings[1][::-1])
t = int(input())
for i in range(0, t):
	n = int(input())
	test_string = input()
	test_string = ' '.join(test_string)
	s = test_string.split(' ')
	x = reverse_per_vowel(s)
	print(x)


def find(a):
	if a == 'a' or a == 'e' or a == 'i' or (a == 'o') or (a == 'u'):
		return True
	return False
for _ in range(int(input())):
	n = int(input())
	s = input()
	(p1, p2) = ([], [])
	sub = 1
	for i in range(n - 1, -1, -1):
		if sub == 1:
			p1.append(s[i])
			if find(s[i]):
				sub = 0
		else:
			p2.append(s[i])
			if find(s[i]):
				sub = 1
	for i in range(len(p2)):
		print(p2[i], end='')
	for i in range(len(p1) - 1, -1, -1):
		print(p1[i], end='')
	print()


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	v = ['a', 'e', 'i', 'o', 'u']
	p = []
	q = []
	x = True
	y = False
	for i in range(len(s) - 1, -1, -1):
		if s[i] not in v:
			if x == True:
				p.append(s[i])
			else:
				q.append(s[i])
		elif x == True:
			p.append(s[i])
			x = False
			y = True
		else:
			q.append(s[i])
			y = False
			x = True
	p.reverse()
	z = q + p
	print(''.join(z))


import re
for _ in range(int(input())):
	n = int(input())
	s = input()
	v = {'a', 'e', 'i', 'o', 'u'}
	ans = [' ' for i in range(n)]
	i = n - 1
	l = 0
	r = n - 1
	R = 0
	while l != r:
		if R:
			ans[l] = s[i]
			l += 1
		else:
			ans[r] = s[i]
			r -= 1
		if s[i] in v:
			R = 1 - R
		i -= 1
	ans[ans.index(' ')] = s[0]
	print(''.join(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = [i for i in s]
	hi = n - 1
	while hi >= 0 and s[hi] not in 'aeiou':
		hi -= 1
	hi -= 1
	(st, ed, d, idx) = (0, hi, 0, hi)
	while idx >= 0:
		temp = []
		while idx >= 0:
			if s[idx] in 'aeiou':
				temp.append(s[idx])
				idx -= 1
				break
			else:
				temp.append(s[idx])
			idx -= 1
		if d & 1:
			for i in temp:
				ans[ed] = i
				ed -= 1
		else:
			for i in temp:
				ans[st] = i
				st += 1
		d += 1
	astr = ''.join(ans)
	print(astr)


for _ in range(int(input())):
	n = int(input())
	s = input()
	strt = 0
	i = 2
	st = []
	while i < len(s):
		if s[i] in {'a', 'e', 'i', 'o', 'u'}:
			st.append(s[strt:i])
			strt = i
		i += 1
	(rt, lt) = ([], [])
	for (i, x) in enumerate(st):
		if i % 2 == 0:
			rt.append(x)
		else:
			lt.append(x)
	res = ''.join(lt)[::-1] + ''.join(rt)
	if len(st) % 2 == 0:
		res += s[strt:]
	else:
		res = res[::-1] + s[strt:]
	print(res)


for _ in range(int(input())):
	n = int(input())
	if 23243 == 32432432342:
		print('Tanmay')
	s = input()
	c = 0
	for i in s:
		if i in ['a', 'e', 'i', 'o', 'u']:
			c += 1
	if s[0] not in ['a', 'e', 'i', 'o', 'u']:
		c += 1
	m = n
	l = ''
	for i in range(n - 1, -1, -1):
		m = i
		l += s[i]
		if s[i] in ['a', 'e', 'i', 'o', 'u']:
			break
	s1 = ''
	f = False
	s2 = ''
	for i in range(m):
		if s[i] in ['a', 'e', 'i', 'o', 'u']:
			if i != 0:
				f = not f
		if f:
			s2 += s[i]
			continue
		s1 += s[i]
	if c % 2 == 0:
		print(s1[::-1] + s2 + l[::-1])
		continue
	print(s2[::-1] + s1 + l[::-1])


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	c = [0 for i in range(len(l))]
	pre = 0
	for i in reversed(range(0, len(l))):
		c[i] = pre
		if l[i] in ['a', 'e', 'i', 'o', 'u']:
			pre += 1
	s1 = ''
	s2 = ''
	for i in range(len(l)):
		if c[i] % 2 == 0:
			s1 += l[i]
		else:
			s2 = l[i] + s2
	print(s2 + s1)


t = int(input())
while t:
	n = int(input())
	s = input()
	first = 0
	l1 = []
	last = 0
	for i in range(0, len(s)):
		if s[i] in 'aeiou':
			last = i
			res = s[first:i]
			first = i
			if res != '':
				l1.append(res)
	l1.reverse()
	pre = ''
	post = ''
	for i in range(0, len(l1)):
		if i % 2 == 0:
			pre = pre + l1[i][::-1]
		else:
			post = l1[i] + post
	ans = pre + post + s[last:]
	print(ans)
	t = t - 1


def main():
	for _ in range(int(input())):
		N = int(input())
		s = input()
		res = []
		p = 0
		for i in range(1, N):
			if s[i] in ['a', 'e', 'i', 'o', 'u']:
				res.append(s[p:i])
				p = i
		l = s[p:]
		e = ''
		o = ''
		r = ''
		for i in range(0, len(res), 2):
			o += res[i]
			if i + 1 < len(res):
				e += res[i + 1]
		if len(res) & 1:
			print(o[::-1] + e + l)
		else:
			print(e[::-1] + o + l)
main()


import math
l = ['a', 'e', 'i', 'o', 'u']
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	ind = 0
	for i in range(n - 1, -1, -1):
		if s[i] in l:
			ind = i
			break
	ss = ''
	l1 = []
	for i in range(n):
		if s[i] in l:
			if len(ss) != 0:
				l1.append(ss)
			ss = s[i]
		else:
			ss += s[i]
	nn = len(l1)
	ans = ''
	for i in range(nn - 1, -1, -2):
		ans += l1[i][-1::-1]
	jj = 0
	if nn % 2:
		jj = 1
	for i in range(jj, nn, 2):
		ans += l1[i]
	for i in range(ind, n):
		ans += s[i]
	print(ans)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class DoublyLL:

	def __init__(self):
		self.head = None
		self.tail = None

	def ppend(self, data):
		new_node = Node(data)
		if self.head is None and self.tail is None:
			self.head = new_node
			self.tail = new_node
			return
		new_node.next = self.head
		self.head.prev = new_node
		self.head = new_node

	def append(self, data):
		new_node = Node(data)
		if self.head is None and self.tail is None:
			self.head = new_node
			self.tail = new_node
			return
		new_node.prev = self.tail
		self.tail.next = new_node
		self.tail = new_node
T = int(input())
for t in range(T):
	N = int(input())
	line = input()
	dll = DoublyLL()
	append = True
	for c in line:
		if c in ['a', 'e', 'i', 'o', 'u']:
			append = not append
		if append:
			dll.append(c)
		else:
			dll.ppend(c)
	newll = []
	temp_node = dll.head
	while temp_node.next:
		newll.append(temp_node.data)
		temp_node = temp_node.next
	newll.append(temp_node.data)
	newl = ''.join(newll)
	if append:
		print(newl)
	else:
		print(newl[::-1])


from collections import deque

def func():
	n = int(input())
	l = input()
	s = {'a', 'e', 'i', 'o', 'u'}
	d = deque()
	f = False
	c = 0
	for i in l:
		if i in s:
			f = not f
			c += 1
		if f:
			d.append(i)
		else:
			d.appendleft(i)
	if c % 2 == 1:
		print(''.join(d))
	else:
		print(''.join(d)[::-1])
t = int(input())
for _ in range(t):
	func()


for h in range(int(input())):
	temp = []
	k = ''
	f = 0
	(a, b) = ('', '')
	n = int(input())
	s = input()
	for i in s:
		if i in ['a', 'e', 'i', 'o', 'u']:
			temp.append(k)
			k = ''
		k += i
	temp.append(k)
	for i in range(len(temp)):
		if i % 2 == 0:
			a += temp[i]
		else:
			b += temp[i]
	if len(temp) % 2 != 0:
		print(''.join(list(reversed(b))) + a)
	else:
		print(''.join(list(reversed(a))) + b)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	vowels = []
	segments = []
	prev = 0
	last = 1
	for i in range(n):
		if s[i] in {'a', 'e', 'i', 'o', 'u'}:
			segments.append(s[prev:i])
			prev = i
	segments.append(s[prev:len(s)])
	for i in range(len(segments) - 2, -1, -2):
		print(segments[i][::-1], end='')
		last = i
	if last == 1:
		start = 0
	else:
		start = 1
	for i in range(start, len(segments), 2):
		print(segments[i], end='')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s1 = ''
	s2 = ''
	ans1 = ''
	count = 0
	for i in range(n):
		if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			count += 1
			if count % 2 == 1:
				ans1 = s1 + ans1
				s2 = s1 = ''
			else:
				ans1 += s2
				s2 = s1 = ''
		s1 = s[i] + s1
		s2 += s[i]
	if count % 2 == 1:
		print(ans1 + s2)
	else:
		print(ans1[::-1] + s2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	sl = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		sl[i] = s[i]
		if s[i] in {'a', 'e', 'i', 'o', 'u'}:
			break
	k = i
	df = k - 1
	dr = -1
	for i in range(k - 1, -1, -1):
		if s[i] in {'a', 'e', 'i', 'o', 'u'} and i > 0:
			sl[df + dr * i] = s[i]
			df = df + dr * (i - 1)
			dr = -dr
		else:
			sl[df + dr * i] = s[i]
	for x in sl:
		print(x, end='')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	v = 'aeiou'
	l = []
	cur = ''
	for i in range(n):
		if s[i] in v:
			if cur != '':
				l.append(cur)
			cur = s[i]
		else:
			cur += s[i]
	l.append(cur)
	if len(l) % 2 == 1:
		ans = ''
		flag = False
		for i in l:
			if flag:
				ans = i[::-1] + ans
				flag = False
			else:
				ans = ans + i
				flag = True
	else:
		ans = ''
		flag = True
		for i in l:
			if flag:
				ans = i[::-1] + ans
				flag = False
			else:
				ans = ans + i
				flag = True
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	n = len(S)
	vpos = [i for i in range(n) if S[i] in 'aeiou']
	v = [S[i] for i in range(n) if S[i] in 'aeiou']
	last = -1
	cval = []
	for i in vpos:
		cval.append(S[last + 1:i])
		last = i
	end = [S[last + 1:]]
	start = []
	pos = len(cval) - 1
	while pos >= 0:
		end.append(v[pos])
		start.append(cval[pos][::-1])
		pos -= 1
		if pos < 0:
			break
		start.append(v[pos])
		end.append(cval[pos])
		pos -= 1
	print(''.join(start + end[::-1]))


for _ in range(int(input())):
	(_, s) = (input(), input())
	curr = ''
	l = []
	for i in s:
		if i in 'aeiou':
			l.append(curr)
			curr = i
		else:
			curr += i
	l.append(curr)
	l = l[::-1]
	fine = ''
	fino = ''
	for (i, j) in enumerate(l):
		if i % 2 == 0:
			fine = j + fine
		else:
			fino += j[::-1]
	print(fino + fine)


def rev(string):
	string = ''.join(reversed(string))
	return string
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	vow = ['a', 'e', 'i', 'o', 'u']
	bits_ = []
	curr_bit = ''
	for i in range(1, n + 1):
		curr_bit += s[-i]
		if i == n:
			bits_.append(curr_bit)
		elif s[-i] in vow:
			bits_.append(curr_bit)
			curr_bit = ''
	(front, back) = ('', '')
	for i in range(len(bits_)):
		if i & 1:
			front += bits_[i]
		else:
			fa = rev(bits_[i])
			back = fa + back
	ans = front + back
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s1 = ''
	s2 = ''
	vowel = 'aeiou'
	v_idx = n
	flag = 0
	for i in range(n - 1, -1, -1):
		if s[i] in vowel:
			if flag == 0:
				s2 = s[i:v_idx] + s2
				v_idx = i
				flag = 1
			else:
				s1 = s1 + s[v_idx - 1:i:-1] + s[i]
				v_idx = i
				flag = 0
	if v_idx > 0 and flag == 1:
		s1 = s1 + s[v_idx - 1::-1]
	elif v_idx > 0 and flag == 0:
		s1 = s1 + s[0:v_idx]
	print(s1 + s2)