Tiny - 2

나이가 지긋한 사람들은 Alexey Pajitnov가 만든 유명한 컴퓨터 게임 "TETRIS"를 아직도 기억한다. 이 게임에서는 네 칸짜리 블록(테트로미노)이 하늘에서 떨어진다. 목표는 블록마다 회전시켜 직사각형 통에 내려놓고, 빈틈없이 채워진 줄을 가능한 한 많이 만드는 것이다. 그런 줄이 만들어지면 줄은 사라지고, 뒤에 오는 블록이 놓일 공간이 넓어진다.

이제 이 게임의 더 단순한 버전인 "Tiny TETRIS"(줄여서 "Tiny")를 살펴보자. Tiny 블록(t-piece)은 한 칸에서 세 칸으로 이루어진 아홉 종류뿐이다.

번호는 t-piece의 종류를 나타내며, 이후 특정 t-piece를 가리킬 때 쓴다.

게임의 목표는 같다. 떨어지는 t-piece를 가로 9칸, 세로 9칸인 직사각형 통에 넣어야 한다. TETRIS와 달리 t-piece는 회전할 수 없다. 또 떨어지기 시작한 뒤에는 좌우로 옮길 수 없다. 따라서 플레이어는 블록마다 가장 왼쪽 칸(×로 표시된 칸)이 떨어질 열 번호(1에서 9 사이의 정수)만 고르면 된다.

한 게임은 N개의 t-piece로 이루어진 유한한 순서열이다. 통의 윗부분을 넘거나 불법 동작을 하지 않고, 가능한 한 많은 t-piece를 통에 넣어야 한다. 게임 점수는 성공적으로 떨어뜨린 t-piece의 개수다.

처음에 게임 카운터는 0이다. 게임 진행 순서는 다음과 같다.

1. 플레이어가 현재 t-piece의 가장 왼쪽 칸을 놓을 열을 고른다.
2. 열이 올바르게 설정되었으면(예를 들어 t-piece 5는 8열이 절대 올바를 수 없다) t-piece는 장애물에 닿을 때까지 떨어진다. 그렇지 않으면 게임이 끝난다.
3. t-piece가 통 안에 완전히 들어가면(모든 칸이 9×9 직사각형 안에 있으면) 카운터를 1 올린다. 그렇지 않으면 게임이 끝난다.
4. 완성된 가로줄(빈틈없이 블록으로 채워진 줄)이 있는지 확인한다. 있으면 그 줄들은 사라지고, 그 위의 줄들은 모양을 유지한 채 아래로 내려온다.
5. 남은 t-piece가 있으면 1)로 돌아간다. 없으면 게임이 끝난다.

게임이 끝났을 때의 카운터 값이 그 게임의 점수다.

하나의 게임을 분석해 보자.

주어진 t-piece 20개의 순서는 5,4,1,6,7,6,4,4,7,9,5,5,6,8,3,4,3,7,4,2이다. 처음 17개의 t-piece는 각각 1,2,2,4,8,8,7,4,8,6,1,1,4,8,3,7,7열에 이미 성공적으로 떨어졌다고 하자. 지금까지 완성된 줄은 없고, 카운터는 17이며, 이제 t-piece 7을 떨어뜨릴 차례다(그림의 문자는 t-piece에 차례로 붙인 것이다).

t-piece 7을 떨어뜨릴 수 있는 유효한 열은 두 곳뿐이다.

a) 1열:	b) 5열(이 경우 줄 하나가 완성되어 사라진다):

각각 한 게임을 설명하는 파일 다섯 개가 주어진다. tiny.i01, tiny.i02, tiny.i03, tiny.i04, tiny.i05다. 각 파일은 t-piece 순서를 담고 있으며 형식은 다음과 같다. 첫 줄에는 정수 N이 하나 있다. 이어지는 N개의 줄이 t-piece 순서를 나타내며, 각 줄에는 1에서 9 사이의 정수, 즉 해당 t-piece의 번호가 있다. t-piece는 통에 떨어뜨려야 하는 순서대로 주어지며, i번째 t-piece는 파일의 i+1번째 줄에 있다.

주어진 입력 파일마다 최대 N행의 출력 파일을 제출해야 한다. 출력 파일의 i번째 행에는 입력 데이터의 i번째 t-piece를 떨어뜨릴 열 번호가 있어야 한다.

각 입력 파일에 대해 모든 t-piece를 통에 성공적으로 떨어뜨릴 수 있는 열의 순서가 존재함이 보장된다(게임 점수가 N이 되는 순서다).