Rotation and Queries

You will be given a string S consisting of lowercase English characters and N queries. In each query, you have to find the lexicographically largest string rotation that has a suffix of the original string with a length of X as a substring. For example:
In given sample, bca string has 3 rotations, bca ($0^{th}$ rotation), cab ($1^{st}$ rotation), abc ($2^{nd}$ rotation) respectively. Among these rotations, there are two rotations that have ca (a suffix of the original string with a length of 2 ) as substring. Between these two rotations, the later one is lexicographically larger. So, the answer to the second query ( query with X = 2) of the first testcase of the sample i/o is 1 (index of rotation).

In case of multiple possible output, i.e. multiple lexicographically equal rotation, output the one with the lowest index of rotation.

A substring is a contiguous sequence of characters within a string. For example, abc has 5 non-empty substrings: a, b, c, ab, bc, abc.
A suffix of a string is any substring of the string which includes its last letter, including itself. For example, abc has 3 suffix: abc, bc, c.
Removing first character of a string and appending it to the end is known as string rotation. For example, the string abc has three different rotations:

• $0^{th}$ rotation is abc itself.

• $1^{st}$ rotation is bca.

• $2^{nd}$ rotation is cab.

Here, we are defining $i^{th}$ rotation as the index of rotation.

Lexicographical ordering means dictionary order. For example, in dictionary trick comes after tracks because ‘i ‘ comes after ‘a’ in English alphabetic system. Remember, this ordering is not based on length of the string. So, lexicographically largest rotation means the rotation that comes last in dictionary among all the rotations.

Input

There will be multiple test cases. The first line will contain an integer T, the number of test cases. In the first line of each case, you’ll be given a string S and an integer N, the original string and the number of queries respectively. Then the next N lines of each test case will contain an integer X, the length of the suffix.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ X ≤ Length of the input string S

For Subtask 1 (10 Points):

• 1 ≤ N ≤ 100

• 1 ≤ Length of the string S ≤ 100

For Subtask 2 (25 Points):

• 1 ≤ N ≤ 3000

• 1 ≤ Length of the string S ≤ 3000

For Subtask 3 (65 Points):

• 1 ≤ N ≤ 100000

• 1 ≤ Length of the string S ≤ 100000

Output

For each test case, you have to print “Case C:” (without quotation mark), where C represents the case number and then each of the next N lines will contain an integer, the answer to the each query, which is the index of the rotation, that is the lexicographically largest string rotation that has a suffix of the original string with a length of X as a substring. Remember, In case of multiple possible output, i.e. multiple lexicographically equal rotation, you have to output the one with the lowest index of rotation.

See the sample i/o for better illustration.

Sample

2
bca 3
1
2
3
abbdef 6
1
2
3
4
5
6

Case 1:
1
1
0
Case 2:
5
4
3
2
1
0