|Contests||Virtual Contests||Problems||Submit||Runs Status||Rank List||Forum|
Luckily John has a lot of friends that want to help carrying his boxes up. They all walk the stairway at the same speed of 1 floor per minute, regardless of whether they carry a box or not. The stairway however is so narrowthat two persons can't pass each other on it. Therefore they deciced to do the following: someonewith a box in his hands is always moving up and someone empty-handed is always moving down. When two persons meet each other somewhere on the stairway, the lower one (with a box) hands it over to the higher one (without a box). (And then the lower onewalks down again and the higher one walks up.) The box exchange is instantaneous. When someone is back on the ground floor, he picks up a box and starts walking up. When someone is at the penthouse, he drops the box and walks down again.
After a while the persons are scattered across the stairway, some of them with boxes in their hands and some without. There are still a number of boxes on the ground floor and John is wondering how much more time it will take before all the boxes are up. Help him to find out!
One line with a positive number: the number of test cases. Then for each test case:
One line with the amount of time (in minutes) it will take to get all the remaining boxes to the penthouse.
2 3 10 5 0 0 0 0 0 0 2 5 1 2 1 3 0