EIU Programming Practices and Exams

This is a continue problem of  http://www.spoj.com/EIUDISC2/problems/EIUCUBES/

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 n_i (1 ≤ n_i ≤ 10¹⁸), 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

Example

Input:
10 106 999 957 24 873 571 658 248 173 600

Output:
7 17 16 4 16 14 14 10 9 14