Song

A rabbit instrument has 26 notes, written with the uppercase English letters A to Z. Writing these letters in a row gives a rabbit song, and one letter means playing that note for one beat. The length of a song is the number of letters. For example, AASDFG is a song of length 6: beat 1 plays A, beat 2 plays A, beat 3 plays S, beat 4 plays D, beat 5 plays F, and beat 6 plays G.

A rabbit psychologist found that the happiness of the note on beat $i+1$ is decided by the pair made of the note on beat $i$ and the note on beat $i+1$. The values sit in a note happiness table, and the table differs from rabbit to rabbit. A row of the table is the note on beat $i$ and a column is the note on beat $i+1$, both in order from A to Z. Write $s(x, y)$ for the value in row $x$ and column $y$. The note on beat 1 gives no happiness, so the song AASDFG gives happiness $s(A, A) + s(A, S) + s(S, D) + s(D, F) + s(F, G)$.

You are given a note happiness table, the first note of a song, and the length of the song. Find the largest happiness such a song can give.

The first line has the number of test cases $T$ ($1 \le T \le 10$). Each test case is made of the following.

1. The note happiness table, given on 26 lines. Each line has 26 happiness values $s_{ij}$ separated by spaces ($0 \le s_{ij} \le 100$). The $j$-th value on the $i$-th line is the happiness of playing the $j$-th note right after the $i$-th note, and the notes run from A to Z.
2. The next line has the number of questions $N$ ($1 \le N \le 10$).
3. Each of the next $N$ lines has an uppercase English letter $C$, the first note of the song, and the length $L$ of the song, separated by a space ($1 \le L \le 100000$).

For each question, print the largest happiness of a song of length $L$ that starts with the note $C$. Print one value per line, in the order the questions are given.