经过一场艰苦的战斗，李将军取得了伟大的胜利。现在，国家元首决定以荣誉和财富来奖励他所做的伟大贡献。

其中一件宝物是一条由26种不同宝石组成的项链，项链的长度为n的链状结构（也就是说：n种宝石串在一起构成了这条项链，每种宝石只属于26种宝石中的一种。项链是链而不是环）

根据古典观点，项链是有价值的，如果而且只有当它是回文（项链在正反方向上看起来都一样）。然而，我们上面提到的项链可能不是一开始的回文。所以国家元首决定把项链切成两半，然后把它们都交给李将军。

同一种类的宝石都有相同的价值（可能是正的，也可能是负的，因为它们的质量-有些种类很漂亮，而有些则看起来像普通的宝石）。回文项链的价值等于宝石的价值之和。而不是回文的项链的值为零。

现在的问题是：如何切割给定的项链，使两个项链的价值之和最大。输出这个值。

有多组输入数据，
第一行，一个整数T (1 ≤ T ≤ 10)表示测试数据的数目，对于每组测试数据：
第一行，26个空格间隔的整数v1, v2, ..., v26 (-100 ≤ vi ≤ 100, 1 ≤ i ≤ 26), 表示每种宝石的价值。
接下来一行，一个由小写字母构成的长度不超过500000的字符串，表示项链，26个字母代表26种宝石，'a'的价值是v1,'b'的价值是v2...'z'的价值是v26

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