**Time limit:**1.00 s**Memory limit:**256 MB

Your task is to remove all but four letters, so that the remaining letters form the word "HIIT". You cannot change the order of the letters.

How many ways there are to do this?

**Input**

The first input line contains an integer $t$: the number of test cases.

After this, $t$ lines follow. Each line contains a string of $n$ letters.

**Output**

For each test case, output the number of ways to form the word "HIIT".

**Constraints**

- $1 \le t \le 100$

- $1 \le n \le 10^5$

- the sum of all $n$ values is at most $10^6$

**Example**

Input:

`3`

HXIIYT

AYBABTU

HIITHIIT

Output:

`1`

0

8