To earn some quick pocket money, Lisa participates in an experiment at the Faculty of Economics. The experiment involves a rather unusual type of currency. Lisa first receives a coin with an integer value Z. She can exchange a coin for lower-value coins, receiving 3 coins with values Z/2, Z/3, and Z/4. She can perform as many exchanges as she wants.
Since banks naturally charge fees even in this currency system, values are always rounded down. Exchanging lower-value coins for higher-value ones is not possible.
At the end of the experiment, Lisa can exchange her coins 1:1 for Euros and keep the money. Of course, she wants to maximize her profit and therefore asks you to write a small program to calculate it.
The first line of input contains the number of test cases that follow. Each test case consists of a number Z, which represents the value of the initial coin (0 ≤= Z < 2^31).
The line feed used is \n.
The maximum Euro amount that Z can be exchanged for. One line per test case, a line can end with \r\n or \n.
2 16 5
17 5
Please log in to submit a question...
Please log in to submit a solution...