Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Biswa and Picnic

Limits: 1s, 256 MB

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.

Fig.: Picture of the first 8 rows in 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:

  • from the front of the queue to the first row in the aisle
  • between adjacent positions in the queue
  • between adjacent seats on same row
  • between adjacent rows in the aisle
  • from a row in the aisle to any aisle adjacent seat on the same row

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.

Input

First line of the test case contains the number T (1 ≤ T ≤ 240), denoting the number of classes in the department. Then T lines follow and in each line i (1 ≤ i ≤ T), there’s a number N (1 ≤ N ≤ 240), denoting the number of students in i-th class).

Output

For each class, you have to print the minimum possible time when everyone can reach their assigned seat.

Samples

InputOutput
1
2
3

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.

Author
  • SakibulMowla's Avatar

    SakibulMowla

Discussion
Submit

Login to submit

Editorial

Login to unlock editorial