SP28315 WEAKSMK - Shoumiks Weakness

Shoumik loves problem solving but he is weak in string related problems. So he is practicing string related problems. But he thought that creating a string related problem and solving that would be a great idea to be strong in strings. So he thought of a problem. Given a string S of N lower case alphabets how many distinct substrings T are there with length L( L=|T| ) and S contains exactly X occurrences of T. In the string S=“abcbcb” the substring T=“bcb” has length L=3 and S has X=2 occurrences of T.(See hints for more clarification) But as Shoumik is weak in string, he is stuck with this problem. You have to help him answering Q queries for a given string S. ### Input First line of input will contain the number of test cases Ts. Then Ts test cases follows. Every test case contains two integers N and Q in the first line. Next line will contain a string S, consisting of N lower casecharacters. The next Q lines will contain Q queries with two integers L,length of T for this query and X, Occurrences of T in S. 1

N/A

N/A