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) ]
hide comments
sherlock11:
2018-06-30 18:59:53
similar problem EMOTICON or rather i say exact same problem |
|
kushwah121:
2018-06-30 08:51:05
Easy Problem !!! Last edit: 2018-06-30 12:09:28 |
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 |