Biswa’s department is going on a picnic and as usual, he is a member of the organizing committee. This time, he is in charge of transportation. He has decided to allocate a bus for each class of the department.
All the buses are of same configuration. There are 40 rows in a bus and each row has exactly 6 seats. There is an aisle in the middle to move inside the bus. So in each row, there are 3 adjacent seats on both sides of the aisle. Rows are numbered from 1 to 40 and seats are labeled as A, B, C, D, E, F on each row. A, B, C are adjacent on one half of the row whereas D, E, F are adjacent on the other.
Here is a picture of the first 8 rows of the bus:
At the beginning, there is a queue in front of all the buses. All the students from a particular class are waiting in the queue in front of their allocated bus.
Everyone in a queue starts moving at the 0-th second. It takes exactly one second to move:
It can be safely assumed that the aisle is divided into 40 rows as well.
Biswa has to assign seats for everyone in a way so that the time when everyone has reached their assigned seat is minimized. That is, the time, when the latest person (not necessarily the last person on the queue) reaches his or her allocated seat, is as little as possible.
First line of the test case contains the number (), denoting the number of classes in the department. Then lines follow and in each line (), there’s a number (), denoting the number of students in -th class).
For each class, you have to print the minimum possible time when everyone can reach their assigned seat.
One possible assignment that minimizes the required time is, assigning first person in the queue to seat D in the first row and assigning second person in the queue to seat C in the first row.
At the end of the 1st second, first person in the queue moves to first row in the aisle, second person in the queue moves to the front of the queue.
At the end of 2nd second, first person moves from first row in the aisle to seat D in the first row, second person moves from front of the queue to first row in the aisle.
At the end of 3rd second, second person moves from first row in the queue to seat C in the first row.