Given a string consisting of lowercase English letters. Each lowercase letter has a corresponding weight . The weight of a subsequence is defined as the product of weights of all its characters.

Let be the maximum possible weight among all subsequences of the given string. Among all subsequences with weight exactly , find the one with maximum length and your task is to output the length.

A subsequence is obtained by deleting zero or more characters from the original string without changing the order of remaining characters. For example,  is a subsequence of string , but  is not.

The first line contains an integer  (), denoting the number of test cases.

For each test case, the first line contains  integers  (), denoting the weight of character , , , ,  respectively. The second line contains a string  (), consisting of only lowercase English letters.

For each test case, print a single integer: the length of the longest subsequence having the maximum possible weight.

1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
hduiaghiukqwbbdopceqweqwcgtrewwaaxcbmn

12

The 26 integers in the example input are on different rows, just for visual convenience. The real test data has all 26 integers on the same line.