Before building the pyramid, Beo went to check the number of bricks. Beo discovered that there were k different types of bricks that could not be used together. Bao decided to build k pyramids, each pyramid using only one type of brick

For each type of brick, help Beo calculate how tall the pyramid is

Input

Consist of 1 line, the first number is k (1 ≤ k ≤ 1000). then followed by k integers ~ni~ (1 ≤ ~ni~ ≤ ~10^{18}~), which is the number of bricks of type ~i~

Output

Output the result in one line, containing k integers corresponding to the height of the ~i-th~ pyramid

Sample Input

10 106 999 957 24 873 571 658 248 173 600

Sample Output:

7 17 16 4 16 14 14 10 9 14