10단계 안에 멈추는 튜링 기계

앨런 매시슨 튜링은 영국의 수학자이자 컴퓨터 과학자다. 그는 계산을 수학적 모형으로 정의한 추상 기계인 튜링 기계를 제시했다.

튜링 기계에는 유한한 상태 집합, 양쪽으로 끝없이 이어지는 테이프, 테이프에 쓸 수 있는 기호 집합, 전이 규칙이 있다. 기계는 시작 상태에서 테이프의 한 칸에 헤드를 올려놓고 동작을 시작한다. 매 단계마다 현재 상태와 헤드가 가리키는 기호를 읽고, 그에 해당하는 전이 규칙이 그 칸에 쓸 기호, 헤드가 움직일 방향, 다음 상태를 정해 준다. 기호를 먼저 쓰고 그다음에 헤드를 움직인다.

정지 문제는 주어진 튜링 기계가 주어진 입력 테이프에서 언젠가 멈추는지, 아니면 영원히 돌아가는지를 묻는다. 모든 기계에 대해 이 질문을 판정하는 알고리즘은 없다. 반면 10단계 안에 멈추는지는 판정할 수 있다. 그 답을 구해야 한다.

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

각 테스트 케이스는 튜링 기계 하나의 정의로 시작한다. 정의의 첫 줄에는 상태의 개수 $n$ ($1 \le n \le 10$)이 주어진다. 상태 $1$이 시작 상태이고 상태 $n$이 유일한 정지 상태다. 기계는 상태 $n$에 들어가는 즉시 멈춘다. $n = 1$이면 기계는 한 단계도 밟기 전에 이미 정지 상태에 있다.

다음 $n - 1$개 줄에는 상태 $1$부터 상태 $n - 1$까지의 전이 규칙이 주어진다. 상태 $n$에는 전이 규칙이 없다. 테이프에 나오는 기호는 $0$, $1$, $2$ 세 가지뿐이다. $i$번째 줄에는 (x, y, z) 꼴의 세 쌍이 공백으로 구분되어 주어지고, 차례로 상태 $i$가 기호 $0$, $1$, $2$를 읽었을 때의 규칙이다. 한 쌍에서 $x$는 다음 상태 ($1 \le x \le n$), $y$는 헤드가 움직이는 방향으로 $1$은 오른쪽이고 $-1$은 왼쪽이며, $z$는 헤드를 움직이기 전에 현재 칸에 쓸 기호다. 예를 들어 다섯째 줄의 두 번째 쌍은 상태 $5$에서 헤드가 기호 $1$을 읽었을 때의 규칙이다.

기계 정의 다음 줄에는 질의의 개수 $m$ ($0 \le m \le 100$)이 주어진다. 질의는 한 줄에 하나씩 주어진다. 먼저 입력 기호의 개수 $x$ ($0 \le x \le 10$)가 오고, 그 뒤에 기호 $x$개가 온다. 이 기호는 주어진 순서대로 테이프의 연속한 칸에 쓰이고, 헤드는 그중 첫 칸을 가리킨 채 시작한다. 질의에는 기호 $0$과 $1$만 나온다. 기호 $2$는 빈 칸을 뜻하기 때문이다. 주어진 기호 앞의 칸과 뒤의 칸은 모두 $2$다. 예를 들어 질의 3 1 0 0은 테이프를 ... 2 2 2 1 0 0 2 2 2 ...로 만들고, 헤드는 기호 $1$을 가리키며, 빈 칸은 양쪽으로 끝없이 이어진다. $x = 0$이면 테이프 전체가 빈 칸이고 헤드도 빈 칸에서 시작한다.

각 테스트 케이스마다 먼저 Machine #N:을 한 줄에 출력한다. $N$은 테스트 케이스의 번호이고 $1$부터 센다. 그다음 질의가 주어진 순서대로 한 줄에 하나씩, 기계가 $10$단계 안에 멈추면 yes, 멈추지 않으면 no를 출력한다. 정확히 $10$번째 단계에서 멈추는 경우도 $10$단계 안에 멈춘 것이다.