튜링 산술식 계산

기계

앨런 튜링은 1936년에 튜링 기계(TM)를 정의했다. 여기서 다루는 기계는 양쪽으로 무한한 테이프, 읽고 쓰는 헤드, 유한 오토마타인 제어 장치로 이루어진다.

테이프는 칸이 일렬로 무한히 늘어선 것이다. 각 칸에는 알파벳 $\Sigma = \{\sim, 0, 1, \dots, M\}$의 기호가 하나씩 들어 있고, $\sim$은 빈칸을 뜻하는 특별한 기호다. 어느 순간에도 빈칸이 아닌 칸은 유한개뿐이다.

헤드는 자기가 서 있는 칸의 기호를 읽고, 그 자리에 다른 기호를 쓰고, 왼쪽이나 오른쪽으로 한 칸 움직인다. 테이프가 양쪽으로 무한하므로 이동은 언제나 가능하다. 제어 장치는 상태 집합 $\Gamma = \{0, 1, \dots, N\}$의 한 상태에 있고, 상태 $0$에서 시작한다. 매 단계마다 현재 상태 $\gamma$와 헤드 아래의 기호 $\sigma$를 보고 그 자리에 쓸 기호 $\sigma'$, 다음 상태 $\gamma'$, 이동 방향 $R$ 또는 $L$을 정한다. 지금 상황에 맞는 규칙이 없으면 기계는 멈추고 계산이 끝난다.

튜링 산술식

튜링 산술식(TAE)은 다음 문법으로 정의한다.

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

+는 10으로 나눈 나머지에서의 덧셈, *는 10으로 나눈 나머지에서의 곱셈이다. 예를 들어 $238 * 17 = 6$이다. 곱셈을 덧셈보다 먼저 계산한다. 변수 $d$는 기계가 시작할 때 테이프에 적혀 있는 $d$번째 정수를 뜻한다.

시작할 때의 테이프

기계가 시작할 때 테이프에는 음이 아닌 정수가 아홉 개 이하로 적혀 있다. 각 정수는 왼쪽에서 오른쪽으로 최상위 자리부터 십진법으로 적히고, 정수 사이는 빈칸 하나로 구분된다. 나머지 칸은 모두 비어 있으며 헤드는 첫 번째 정수의 최상위 자리 위에서 시작한다. 아래 테이프에는 123, 47, 11이 적혀 있고 굵게 쓴 칸이 헤드의 위치다.

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

튜링 기계는 이론적으로 범용 컴퓨터와 같은 계산을 하므로, 어떤 TAE에 대해서도 그 식의 값을 테이프에 남기고 멈추는 기계가 존재한다. 그 기계를 직접 만드는 대신, 기계가 남길 값을 구하면 된다. 위 테이프와 식 (1+3)*2의 값은 $(123 + 11) \times 47 \bmod 10 = 8$이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$). 각 테스트 케이스는 두 줄이다.

첫 줄에는 테이프에 적힌 순서대로 음이 아닌 정수 $K$개가 공백 하나로 구분되어 주어진다 ($1 \le K \le 9$). 각 정수는 십진법으로 100자리 이하이고 앞에 0이 붙지 않는다.

둘째 줄에는 올바른 TAE가 하나 주어진다. 길이는 1000자 이하이고 1부터 9까지의 숫자와 (, ), *, +만 쓰인다. 식에 나오는 변수는 모두 $K$ 이하다.

각 테스트 케이스마다 식의 값을 10으로 나눈 나머지를 한 줄에 하나씩 출력한다. 이 값은 기계가 헤드 아래에 남길 한 자리 숫자다.