You are given a string 
of length 
consisting of lowercase English letters and a non-decreasing array 
.
A set 
of non-empty strings is called good if and only if:
- There does not exist a pair of strings in such that one is a suffix of the other. Here, string
is said to be a suffix of string 
if can be obtained by deleting some letters (possibly, none) in in the beginning.
For a good set , denote the value of as 
, where 
is the length of string 
.
For a string and some positive integer 
, define &preview=true)
as the maximum value among all good sets that satisfies the following conditions:
-
; - only contains substrings of . Here, string is said to be a substring of string if can be obtained by deleting some letters (possibly, none) in in the beginning and some letters (again, possibly none) in the end.
You need to answer 
queries. For each of them, you are given two values 
(
), and you need to find out &preview=true)
, where 
denotes the prefix with 
letters of .
输入描述:
The input consists of multiple test cases.
The first line consists of a single integer - the number of test cases. Then test cases descriptions follow.
The first line of every case consists of two integers 
(
) - the length of the string and the number of queries.
The second line contains the string .
The third line contains positive integers 
(
). It is guaranteed that 
.
For the next lines, each line contains two positive integers 
(
), describing a query.
It is guaranteed that 
.
输出描述:
For each query, print an integer indicating your answer.
示例1
输入
复制
2
8 3
ababaaab
1 2 2 5 7 8 10 10
8 1
1 2
4 4
6 2
abcacb
4 7 9 10 13 49
4 2
6 3