Mozahid and Sharmeen loves each other and spend a lots of time together. One day they found a string which contains only lowercase English letters. As Mozahid loves Sharmeen very much he likes all ‘s’ in the string. On the other hand as Sharmeen loves Mozahid very much she likes all the ‘m’ in the string. Sharmeen always want to stay on both sides (left and right) of Mozahid so that no other girl can take him away from her :P. So, this time Mozahid gives her a task. Mozahid told her, if she can tell him how many different subsequence of ‘sms’ exist in that string, he will ensure her that no girl will take him away from her. As Sharmeen is not a programmer, she needs your help to perform this task. Can you do this for her?

Input

In the first line given an integer T (1 ≤ T ≤ 10), the number of test cases.

In each test case given a string S of size N (1 ≤ N ≤ 10⁵) of lowercase English letters.

Output

For each test case print the number of different subsequence of ‘sms’ exist on that string in one line. For clearance ‘skmjssm’ has 2 different subsequence of ‘sms’.  {1, 3, 5} and {1, 3, 6} (1 based position). For better understanding see the sample input output.

Example

Input:
2
asdfmnsmdsms
ssmssmjm

Output:
10
4

[ This problem originally written by MD. Mozahidul Islam Bhuiyan (kissu_pari_na) ]