MOZHSLM - Sharmeen Loves Mozahid Loves Sharmeen [ HARD ]

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 ≤ 105) 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) ]


Added by:Avik Sarkar
Date:2018-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2018-06-30 18:59:53
similar problem EMOTICON or rather i say exact same problem
2018-06-30 08:51:05
Easy Problem !!!

Last edit: 2018-06-30 12:09:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.