Phil in the Blanks

Time limit1sMemory limit128 MB

Summary

A puzzle sentence has up to four blanks to fill with number words (zero to one hundred); the filled sentence must correctly count letters, vowels, consonants, or given characters including the inserted words. Count solutions.

Level: Medium6 of 10
Topics: Brute force, String, Implementation, Math
Solved: No attempts yet

Problem

Phil is trying to solve a series of puzzles in which he must fill in the blanks of a sentence with number words so that the statement becomes true. Being a programmer, you decide to write a program that finds all the possible solutions. Here is an example puzzle:

There are ___ Os and ___ Ts in this sentence.

One possible solution is to put "two" in the first blank and "five" in the second blank. Note that "one" would not work in the first blank, because the word "one" itself contains one "O" — the words written into the blanks are part of the puzzle and are counted too. Grammar is not considered.

Input

The first line contains a single integer $D$ ( $1 \le D \le 100$ ), the number of data sets. Each of the following $D$ lines contains one puzzle to solve.

Each puzzle is between 1 and 100 characters long (inclusive) and contains between 1 and 4 (inclusive) positive assertions, each of one of the following forms:

___ Cs — the blank is the number of occurrences (upper- and lowercase) of the indicated letter $C$ in the puzzle.
___ letters — the blank is the number of letters in the puzzle.
___ vowels — the blank is the number of vowels in the puzzle; for this problem only A, E, I, O, and U are vowels.
___ consonants — the blank is the number of consonants in the puzzle.

Each blank consists of three underscore characters (_) in a row, and the literal words letters, vowels, and consonants are always lowercase. Any underscore characters appearing in a puzzle are part of a blank.

Output

For each data set, output the number of possible correct solutions. Every number word used ranges from "zero" to "one hundred".

Examples3

Example 1

Input

5
There are ___ Os and ___ Ts in this sentence.
There are ___ Ts and ___ Es in this sentence.
Hey, ___ letters here
And ___ vowels here
with ___ consonants here

Expected output

Example 2

Input

1
There are ___ Os and ___ Ts in this sentence.

Expected output

Example 3
Input
```
1
Hey, ___ letters here
```
Expected output
```
2
```