Суперстрока

Суперстрока состоит из символов латинского алфавита. Гласными считаются буквы: a, e, i, o, u, y, A, E, I, O, U, Y. Требуется посчитать количество способов разбиения заданной суперстроки на слова. Словом считается последовательность букв, содержащая хотя бы одну гласную букву.

Длина строки не превышает 200 символов. Количество разбиений не превышает 2 * 10^9.

Входные данные

В первой строке дано число n (1 ≤ n ≤ 50000). Далее записаны n суперстрок.

Выходные данные

Вывести n чисел – количество возможных вариантов разбиения соответствующей суперстроки.

Примеры