Description

你现在有一个长度为 $n$ 的仅由小写字符组成的字符串 $S$。

每个小写字符的权值为 $w_i$，你现在可以把一些小写字符变成其对应的大写字符。

一个字符串的权值定义为这个字符串内所有小写字符的权值的乘积。

设 $2^n$ 种变换情况中权值最大的字符串的权值为 $V$，对于所有权值等于 $V$ 的情况中，保留的小写字符最多的情况是哪种？由于情况可能过多，本题只需要输出保留最多的小写字符的情况所对应的小写字符个数即可。

Input

第一行一个正整数，表示数据组数 $T$（$1\le T \le 5$）。

对于每一组数据，第一行输入 $26$ 个空格隔开的整数 $v_1,v_2,\cdots,v_{26}$（$0 \le v_i \le 10^9$），分别表示小写字符 $a,b,c,\ldots,z$ 的权值。

第二行输入一个长度为 $n$（$1\le n \le 5\times 10^4$）的仅包含小写字母的字符串 $S$。

Output

对于每一组数据，输出一行一个正整数，表示答案。

Samples

1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
abcde

5

Note

所有字符均为小写字符时，权值最大，为 $2^5=32$。

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛