Snooker

Ronnie owns a very old television. It has no sound, and the picture is so blurry that no text can be read. So when Ronnie watches a snooker match, he can see neither the current score nor which player is at the table -- the only thing he can make out is the colour of each ball that is potted or missed. Ronnie does not care who wins, but he has no interest in a match that is already decided, so we want to detect the exact moment a match becomes decided.

Snooker is a two-player game played on a table with 15 red balls (each worth 1 point) and one each of the yellow, green, brown, blue, pink and black balls (worth 2, 3, 4, 5, 6 and 7 points respectively). The players take turns; during a turn a player pots a run of balls, and the turn passes to the opponent as soon as the player misses a ball.

At the start of every turn a player must first pot a red ball. After a red, the player pots a non-red ball of choice, then a red again, then another non-red, and so on. Potted reds stay off the table, but a potted non-red is returned to the table. When a player pots the last red, the player must again (try to) pot a non-red ball, which is likewise returned to the table.

From then on the non-red balls must be potted in ascending order of value (from 2 up to 7), and they are no longer returned to the table. The game ends when the last ball -- the black -- is potted and the table is empty. One can check that finishing the game takes at least 36 shots.

The player with the higher score wins. If the scores are equal after the black has been potted, the turn does not change: the black is placed back on the table and the first player to pot it wins. We assume that the only mistake a player can make is to miss a ball; in particular, a player never pots the wrong ball (which can happen in the real game).

We call a game decided when the gap between the two scores becomes so large that the player who is behind can no longer possibly win.

For example, if the score is 60-44 and only the black and the pink ball remain, the gap is 16 while the remaining balls are worth only 13, so the game is decided. As another example, suppose a player has just potted a non-red ball and two reds remain (so every non-red ball is also still in play); the most that can still be scored is $1+7+1+7+2+3+4+5+6+7 = 43$, so at a score of 70-26 the game is decided, but at 70-28, or even 70-27, it is not.

The first line contains a single integer: the number of test cases. Each test case has the following format:

• One line with an integer $N$ where $36 \le N \le 1000$: the length of the sequence of shots.
• One line with $N$ integers $v$ where $0 \le v \le 7$: the values of the balls potted in order, where $v = 0$ means the player missed a ball. The integers form a complete, valid game played according to the rules above and ending with the final black ball. The integers are separated by single spaces.

For each test case, print a single line with one integer: the smallest index $i$ (shots are numbered from 1 to $N$) such that the game is decided immediately after shot $i$.