노래

토끼용 악기에는 A부터 Z까지 영어 대문자로 적는 음 26개가 있다. 이 문자를 이어 붙이면 토끼 노래가 되고, 문자 하나는 그 음을 한 박자 연주한다는 뜻이다. 노래의 길이는 문자의 개수다. 예를 들어 AASDFG는 길이가 6인 노래이고, 1박자에 A, 2박자에 A, 3박자에 S, 4박자에 D, 5박자에 F, 6박자에 G를 연주한다.

토끼 심리학자는 $i+1$번째 박자의 음이 주는 행복도가 $i$번째 박자의 음과 $i+1$번째 박자의 음이 이루는 짝으로 정해진다는 사실을 알아냈다. 이 값은 음 행복도 표에 적혀 있고, 표는 토끼마다 다르다. 표의 행은 $i$번째 박자의 음, 열은 $i+1$번째 박자의 음을 뜻하며 둘 다 A부터 Z 순서다. 행이 $x$, 열이 $y$인 칸의 값을 $s(x, y)$라고 하자. 1박자의 음은 행복도를 주지 않으므로 노래 AASDFG의 행복도는 $s(A, A) + s(A, S) + s(S, D) + s(D, F) + s(F, G)$이다.

음 행복도 표와 노래의 첫 음, 노래의 길이가 주어진다. 이 조건을 지키는 노래가 줄 수 있는 가장 큰 행복도를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 10$). 각 테스트 케이스는 다음과 같이 이루어진다.

1. 음 행복도 표가 26줄에 걸쳐 주어진다. 각 줄에는 행복도 $s_{ij}$ 26개가 공백으로 구분되어 주어진다 ($0 \le s_{ij} \le 100$). $i$번째 줄의 $j$번째 값은 $i$번째 음 다음에 $j$번째 음을 연주할 때 얻는 행복도이고, 음의 순서는 A부터 Z까지다.
2. 다음 줄에 질문의 개수 $N$이 주어진다 ($1 \le N \le 10$).
3. 다음 $N$개의 줄에 노래의 첫 음을 나타내는 영어 대문자 $C$와 노래의 길이 $L$이 공백으로 구분되어 주어진다 ($1 \le L \le 100000$).

각 질문마다 첫 음이 $C$이고 길이가 $L$인 노래로 얻을 수 있는 가장 큰 행복도를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.