스누커

Ronnie는 아주 낡은 TV를 가지고 있다. 소리도 나지 않고 화면이 너무 흐릿해서 글자를 읽을 수도 없다. 그래서 Ronnie가 스누커 경기를 볼 때는 현재 점수도, 지금 치고 있는 선수가 누구인지도 알 수 없다. 그가 알아볼 수 있는 것은 포켓되거나 빗나간 공의 색깔뿐이다. Ronnie는 누가 이기는지에는 관심이 없지만, 이미 승부가 결정된 경기에는 흥미가 없다. 그래서 우리는 경기의 승부가 결정되는 바로 그 순간을 찾아내려고 한다.

스누커는 두 사람이 하는 게임으로, 테이블 위에는 빨간 공 15개(각각 1점)와 노랑(2점), 초록(3점), 갈색(4점), 파랑(5점), 분홍(6점), 검정(7점) 공이 하나씩 있다. 두 선수는 번갈아 차례를 가지며, 한 차례 동안 공을 연달아 넣다가 공을 빗나가는 순간 차례가 상대에게 넘어간다.

모든 차례의 시작에서 선수는 먼저 빨간 공 하나를 넣어야 한다. 빨간 공을 넣고 나면 원하는 색의 빨간색이 아닌 공을 하나 넣고, 다시 빨간 공, 다시 빨간색이 아닌 공을 넣는 식으로 번갈아 넣는다. 넣은 빨간 공은 테이블에서 빠지지만, 빨간색이 아닌 공은 넣을 때마다 다시 테이블로 돌아온다. 마지막 빨간 공을 넣은 뒤에도 선수는 빨간색이 아닌 공을 한 번 더 (넣으려고) 시도해야 하며, 이 공도 테이블로 돌아온다.

그다음부터는 빨간색이 아닌 공들을 점수가 작은 것부터 큰 것까지(2부터 7까지) 순서대로 넣어야 하며, 이때부터는 테이블로 돌아오지 않는다. 마지막 공인 검정 공까지 넣어 테이블이 비면 게임이 끝난다. 게임을 끝내려면 적어도 36번의 샷이 필요함을 쉽게 확인할 수 있다.

점수가 더 높은 선수가 이긴다. 마지막 검정 공을 넣은 뒤 점수가 같으면 차례는 바뀌지 않고 검정 공을 다시 테이블에 올려놓으며, 이 공을 먼저 넣는 선수가 이긴다. 선수가 할 수 있는 유일한 실수는 공을 빗나가는 것뿐이라고 가정한다. 특히 선수는 (실제 경기에서는 일어날 수 있는) 엉뚱한 공을 넣는 일은 결코 없다.

어느 순간 두 선수의 점수 차가 너무 커져서 뒤지고 있는 선수가 더 이상 이길 수 없게 되면, 우리는 그 경기가 승부가 결정되었다고 부른다.

예를 들어 점수가 60-44이고 테이블에 검정 공과 분홍 공만 남았다면, 점수 차는 16인데 남은 공의 가치는 13뿐이므로 승부가 결정된 것이다. 또 다른 예로, 어떤 선수가 방금 빨간색이 아닌 공을 넣었고 빨간 공이 두 개 남아 있다면(따라서 모든 빨간색이 아닌 공도 아직 남아 있다), 앞으로 얻을 수 있는 최대 점수는 $1+7+1+7+2+3+4+5+6+7 = 43$이다. 그러므로 점수가 70-26이면 승부가 결정된 것이지만, 70-28이나 심지어 70-27이면 아직 결정되지 않았다.

첫 줄에는 테스트 케이스의 개수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 정수 $N$이 주어진다($36 \le N \le 1000$). 이는 친 공들의 순열 길이이다.
• 한 줄에 $N$개의 정수 $v$가 주어진다($0 \le v \le 7$). 이는 순서대로 포켓된 공들의 가치이며, $v = 0$은 선수가 공을 빗나갔음을 뜻한다. 이 정수들은 위 규칙을 따른 완전하고 유효한 한 판의 경기를 이루며, 마지막 검정 공으로 끝난다. 정수들은 하나의 공백으로 구분된다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 샷은 1부터 $N$까지 번호가 매겨지며, 샷 $i$ 바로 다음에 승부가 결정되는 가장 작은 지수 $i$를 출력하면 된다.