Code Submission Evaluation System Login

HIIT Open 2016

Start:2016-05-28 11:00:00
End:2016-05-28 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2016 - HIIT remains

HIIT remains

Time limit:1.00 s
Memory limit:256 MB

You are given a string that consists of letters A..Z.

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
Example

Input:
3
HXIIYT
AYBABTU
HIITHIIT


Output:
1
0
8