테트리스

테트리스 초고수 배찌는 간식을 걸고 테트리스 내기를 해서 다른 캐릭터의 간식을 뺏어먹는 것이 특기이다. 악명 높은 배찌의 간식 내기를 무서워하는 다른 캐릭터들은 배찌를 막기 위해 테트리스 매크로를 만들기로 결심했다.

테트리스는 $4$개의 격자로 구성된 블록들과, $20 \times 10$ 크기의 격자판으로 하는 간단하고 유명한 퍼즐 게임이다. 규칙은 다음과 같다.

• 게임 처음에 격자판은 비어 있다.
• 게임이 시작되면 지정된 순서대로 다음 $7$개 중 하나의 블록들이 격자판의 위쪽에서 아래쪽으로 떨어지게 된다. 블록은 다른 블록을 만날 때까지 떨어진다.

• 플레이어는 블록이 떨어질 위치를 좌우로 이동시키거나 블록을 회전시킬 수 있다. 단, 일반적인 테트리스와 달리 떨어지는 중간에는 좌우로 이동하거나 회전할 수 없다.
• 블록은 격자판 밖으로 나갈 수 없다. 블록을 어디에 위치시켜도 격자판을 나가는 경우에는 게임이 종료된다.
• 블록이 떨어진 후 블록들로 차있는 행은 없어지며, 그 위의 블록은 아래로 떨어진다.
• 블록을 떨어뜨리기 전에 ‘홀드’라는 기능을 사용할 수 있다. ‘홀드’ 기능을 사용하여 떨어뜨리려는 블록과 ‘홀드 칸’에 있는 블록을 바꿀 수 있다. 게임 처음에 ‘홀드 칸’은 비어있으며, 비어있을 때 사용하면 현재 블록이 ‘홀드 칸’으로 들어간 뒤 다음 블록이 나타난다.
• ‘홀드’ 기능은 연속해서 사용할 수 없다.
• 가장 마지막 블록을 떨어뜨린 뒤 ‘홀드 칸’에 남아있는 블록은 사용할 수 없다.

테트리스 배틀을 이기기 위해서는 최대 콤보가 높아야 한다. 콤보는 다음과 같이 계산된다.

• 게임이 시작할 때의 콤보 수는 $0$이다.
• 블록을 떨어뜨릴 때마다 블록들로 차있는 행이 하나라도 있다면, 콤보가 $1$ 올라간다. 없다면 콤보는 0으로 초기화된다.

배찌에게 간식을 뺏긴 캐릭터들은 힘을 합쳐 매크로를 만들어보려고 했지만, 아무리 해도 높은 콤보를 내는 매크로는 만들 수 없었다. 캐릭터들을 도와 떨어지는 블록의 순서가 주어졌을 때 높은 콤보를 내는 방법을 찾는 프로그램을 작성해주자.

입력 형식

입력은 여러 번의 게임으로 이루어진다.

첫 번째 줄에 게임의 횟수 $T$가 주어진다. ($1 \le T \le 10$)

각 게임의 첫 번째 줄에 블록의 개수 $N$이 주어진다. ($1 \le N \le 100$)

두 번째 줄에 블록이 떨어지는 순서를 나타내는 $N$개의 블록 번호가 주어진다. 블록 번호는 위의 그림에서, 빨간색 블록부터 보라색 블록까지 순서대로 $0$부터 $6$까지의 자연수로 배정된다.

채점에 사용되는 입력데이터는 블록들을 무작위로 생성한 것임이 보장된다.

출력 형식

각 테스트케이스 별로 $N+\max(0, (\textrm{홀드 횟수})-1)$개의 줄에 각 턴에 하는 행동을 출력한다. 홀드 기능을 사용한 경우 $H$를, 사용하지 않은 경우 회전 횟수 $r$과 떨어지는 블록의 가장 왼쪽 위치 $x$를 공백을 사이에 두고 출력한다. ($0 \le r \le 3$, $0 \le x \le 9$)

격자칸의 가장 왼쪽 위치는 $0$이며, 가장 오른쪽 위치는 $9$이다. 블록 회전은 시계 방향으로 $90$도 회전시키는 것을 의미한다.

예제

1
7
0 1 0 0 0 1 0

0 0
H
0 4
0 2
0 6
H
0 0
H
0 8

예제 설명

예제 출력은 $2$콤보이며, $7$번째 줄에서 $1$번 블록으로, $9$번째 줄에서 $1$번 블록으로 각각 한 줄을 제거하였다.

채점 방식

각 테스트케이스의 점수는 아래와 같이 계산된다.

• 출력에 잘못된 내용이 있거나, 블록을 위치시킬 수 없어 게임이 중간에 종료되는 경우 점수를 받지 못한다.
• 위의 경우에 해당되지 않다면, 테스트케이스 각각에 대해
  $$(\textrm{해당 테스트케이스의 점수}) \times \left(0.5 + \frac{0.5(T+1)}{B+1}\right)$$
  를 점수로 받는다. ($T$ = 제출한 답안의 최대 콤보 총합, $B$ = 모든 대회 참가자가 이 문제에 제출한 마지막 답안으로부터 나온 기록 중 가장 큰 최대 콤보 총합)

최종 점수는 모든 테스트케이스 점수의 합이다.

해설