The superstring consists of Latin alphabet. Vowels are considered to be letters a, e, i, o, u, y, A, E, I, O, U, Y. Calculate the number of ways of splitting the given superstring into words. A word is a sequence of letters containing at least one vowel letter.

The length of a substring does not exceed 200 characters. The number of partitions does not exceed 2 * 109.

Input

The first line contains the number n (1 ≤ n ≤ 50000). Then n superstrings are given.

Output

Print n numbers - the number of possible ways to split the corresponding superstring.