Problem Brief

Anti-Aging Serum

INTERNOA

Rick is trying to create an anti-aging formula, which consists of sequence of different molecules (represented by lowercase alphabets here). The longer the sequence, the more effective the formula. He has been visiting different universes to get samples of the chemical for his experiments.

However, due to the struggle between the molecules, the formula becomes unstable if the length of the molecules is more than the tolerance of a molecule in the formula.

Each sample is a string of length n, having lowercase alphabetical characters. For each sample, determine the length of the most effective formula.

Note: The sequence can be a substring only for that sample.

Input Format:

The first line contains n, The number of universes.

Now for each Universe:

The first line contains m, the number of samples.

The next line contains a lowercase alphabetical string of length n.

The next line contains 26 integers a_j, 1 <= a_j <= 10^3, representing the maximum length of the substring in which each character can exist.

Output Format:

Print N lines, where each line has an integer stating the length of the longest sequence.

1Example 1

Input

sample = "baaaccc", tolerance = [6, 4, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Output

Explanation

The longest substring is aaccc, where a can exist in a string of size 6, the same as c.

2Example 2

Input

sample = "abcbddba", tolerance = [4, 7, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Output

Explanation

The longest substring is bcbdd.

Constraints

Limits and guarantees your solution can rely on.

Number of universe n <= 10^5.

Sample length of each universe, m <= 10^3.

The sum of samples in each universe <= 10^6.