We all know that in the game Tetris, we try to put some bricks into a table. The table size is 18 rows and 10 columns. When all cells of a row is filled with bricks, that row is cut and we win one point score.
Nam is playing a game. There are already some bricks on the table. The next brick is a 1x4 rectangle bar (four cells). The bar can be rotated into portrait or landscape. At the beginning, the bar appears at the top of the table and continuously goes down. While going down, the bar can be moved left or right, but not go outside the table, although just one cell. The bar will stop when some existed bricks prevent it goes down or when the bar reaches the bottom of the table. After that, rows will be cut if all their cells is filled with bricks.
Nam is very greedy. He try to cut as many rows as possible. Please help him.
The input starts with T - the number of tests. Then T test follows. Each test is printed in only one line with 10 numbers hi (1 ≤ i ≤ 10; 0 ≤ hi ≤ 18). hi is the height of column i, other words, hi bottom cells of column i are filled with bricks.
It guarantees that the input contains at least one 0 so that there is no “automatically” cut row.
For each test, print a single number: the maximum number of rows that can be cut. If no row is cut, print 0.