You're given a string S of length N consisting of lowercase English letters. You are asked Q queries of the type L R. For each query, you are asked to find the no of good substrings between L to R (inclusive).
A substring will be called good if it has no inversions. If there exists any pair of indices (i,j) in the substring a where, i<j for which ai>aj (according to the alphabetical order of the letters) then this pair is counted as an inversion.
A substring of a string is a continuous segment of letters from the string. For example, "acker" is a substring of "hackerearth" and "ckar" is not. The length of the substring is the number of letters in it.
Input format
- First line of input contains an integer T (the no of test cases). Each test case consists of the followings:
- First line contains an integer N (the length of the string).
- Second line contains a string S consisting of N english lowercase letters.
- Third line contains an integer Q (the no of queries).
- Next Q lines contain three space-separated integers L R denoting the query.
Output format
For each test case, for each ith query, print a single integer denoting the answer to the ith query.
Constraints
1≤T≤101≤N,Q≤2⋅1051≤L≤R≤NS contains lowercase English letters
- For the first query: We have [abc] in which "a", "b", "c", "ab", "bc" and "abc" have no inversions, so the answer is 6.
- For the second query: We have [bc] in which "b", "c" and "bc" have no inversions, so the answer is 3.
- For the third query: We have [ced] in which "c", "e", "d" and "ce" have no inversion whereas "ed" and "ced" have inversions, so the answer is 4.
- For the fourth query: We have [abced] in which "a", "b", "c", "e", "d", "ab", "bc", "ce", "abc", "bce" and "abce" have no inversions where as "ed", "ced", "bced" and "abced" have inversions, so the answer is 11.
