Sum of Floor of Cube Roots

Given a positive integer x, we define the function \(f(x) = \lfloor x^{\frac{1}{3}} \rfloor\), where \(\lfloor x \rfloor\) denotes the greatest integer not exceeding \(x\). For a given query with a positive integer \(x_i\), compute:

[ S(x_i)=\sum_{j=1}^{x_i} \lfloor j^{\frac{1}{3}} \rfloor ]

You are given \(q\) queries. For each query, output the corresponding result.

inputFormat

The first line contains a single integer \(q\) (the number of queries).

Each of the next \(q\) lines contains a positive integer \(x_i\).

\(1 \leq x_i \leq 10^{12}\) (for example).

outputFormat

For each query, output a single line containing the sum \(S(x_i)=\sum_{j=1}^{x_i} \lfloor j^{\frac{1}{3}} \rfloor\).

sample

3
1
8
27

1
9
48