Trong bảng chữ cái tiếng Anh có ~5~ nguyên âm là a, e, i, o, u, còn lại là ~21~ phụ âm.

Xét một xâu ~s~ chỉ gồm các ký tự in thường. Xâu ~s~ được gọi là xâu đặc biệt nếu:

• Có ít nhất một nguyên âm.
• Có ít nhất một phụ âm.
• Các nguyên âm nằm về một phía (trái / phải) của xâu.

Ví dụ, xâu aaab, bhheui là xâu đặc biệt, còn các xâu aaa, aeiou, ababah không phải là xâu đặc biệt.

Cho xâu ~s~. Đếm số xâu con (không cần liên tiếp) của xâu ~s~ là xâu đặc biệt.

Input

Dòng đầu tiên gồm số nguyên dương ~T~ (~1 \le T \le 10^4)~ là số truy vấn.

Mỗi truy vấn gồm xâu ~s~ (~1 \le |s| \le 3 \times 10^5~).

Dữ liệu đảm bảo ~\sum |s| \le 3 \times 10^5~.

Output

~T~ dòng, mỗi dòng là số xâu con (không cần liên tiếp) của xâu ~s~ là xâu đặc biệt.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~20032024~.

Sample Input

5
ab
aab
aba
aaa
code

Sample Output

1
3
2
0
6