Turing Arithmetic Expressions

The machine

Alan Turing defined the Turing machine (TM) in 1936. The machine used here has a two way infinite tape, a read and write head, and a control unit that is a finite automaton.

The tape is an infinite one dimensional sequence of fields. Each field holds one symbol of the alphabet $\Sigma = \{\sim, 0, 1, \dots, M\}$, where $\sim$ is the special blank symbol. At any moment only finitely many fields hold something other than a blank.

The head reads the symbol in the field it stands on, writes another symbol in its place, and moves one field to the left or to the right. The tape is infinite in both directions, so a move is always possible. The control unit is in one state of $\Gamma = \{0, 1, \dots, N\}$ and starts in state $0$. At each step it looks at its current state $\gamma$ and at the symbol $\sigma$ under the head, then fixes the symbol $\sigma'$ written in place of $\sigma$, the next state $\gamma'$, and the direction of the move, $R$ or $L$. When no rule matches the current situation, the machine stops and the computation is finished.

Turing arithmetic expressions

A Turing arithmetic expression (TAE) is defined by this grammar.

TAE      -> expr
expr     -> factor | expr + expr
factor   -> ( expr ) | factor * factor | variable
variable -> 1 | 2 | ... | 9

+ is addition modulo 10 and * is multiplication modulo 10, so $238 * 17 = 6$. Multiplication is computed before addition. The variable $d$ denotes the $d$-th integer written on the tape when the machine starts.

The tape at the start

When the machine starts, the tape holds at most nine non-negative integers. Each integer is written left to right in decimal with the most significant digit first, and one blank separates two neighbouring integers. Every other field is blank, and the head stands on the most significant digit of the first integer. The tape below holds 123, 47 and 11, with the head on the field written in bold.

$\dots \; \sim \; \sim \; \mathbf{1} \; 2 \; 3 \; \sim \; 4 \; 7 \; \sim \; 1 \; 1 \; \sim \; \sim \; \dots$

A Turing machine computes whatever a general purpose computer computes, so for every TAE there is a machine that stops with the value of the expression on the tape. Building that machine takes a lot of work, so report the value it would leave instead. For the tape above and the expression (1+3)*2 that value is $(123 + 11) \times 47 \bmod 10 = 8$.

The first line contains the number of test cases $T$ ($1 \le T \le 100$). Each test case takes two lines.

The first line of a test case contains $K$ non-negative integers in the order they appear on the tape, separated by single spaces ($1 \le K \le 9$). Each integer is written in decimal with at most 100 digits and no leading zero.

The second line of a test case contains one valid TAE. It is at most 1000 characters long and uses only the digits 1 to 9 and the characters (, ), * and +. Every variable in it is at most $K$.

For each test case print the value of the expression modulo 10 on its own line. This value is the single digit the machine would leave under the head.