After solving the problem “MOZHSLM” Sharmeen become familiar with subsequence and somehow become interested in substring. Instead of learning more about substring she started asking some ludicrous questions to Mozahid about substring. Become tired of answering Sharmeen’s ludicrous questions Mozahid gives Sharmeen another problem which is slightly harder than the previous one. Mozahid will give Sharmeen a string of lowercase English letters and some queries. In each query he will give her a substring of that string. Sharmeen has to answer how many different subsequence of ‘sms’ exists in that substring. Can you help Sharmeen solving this problem?

Input

Given a string of lowercase English letters of length N (1 <= N <= 10^5) in first line. In the second line given an integer Q (1 <= Q <= 10^5), which is the number of queries. In each query you will be given two integer L, R (1 <= L <= R <= N). L is the starting position of the substring and R is the ending position of the substring (1 based position).

Output

For each query you have to output an integer in one line which is the number of different subsequence of ‘sms’ in that substring.

N.B. Substring is a consecutive sequence of characters of a string. Where subsequence not necessarily need to be consecutive. But for both you have to maintain the order. 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:
sasmasamsas
3
1 6
3 9
8 11

Output:
2
4
0

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