问题描述

小可可想计算所有不大于 $x$ 的正整数的立方根下取整之和，但是她不会做，你能帮 帮她吗？

为了彻底帮小可可弄懂这个问题，你需要回答 $q$ 组询问，对于每个 $x_i$，输出 $\sum_{j=1}^{x_i}{\lfloor j^{\frac{1}{3}}\rfloor}$。

其中，$\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。

输入

第一行一个正整数 $q$。

接下来 $q$ 行，每行一个正整数 $x_i$，保证所有给出的 $x$ 单调不降。

输出

$q$ 行，每行一个整数，表示答案。请注意答案的范围。

样例 1

2
5
10

5
13

样例 1 解释

$1 ∼ 10$ 的立方根下取整的结果是：$1, 1, 1, 1, 1, 1, 1, 2, 2, 2$。

约定和数据范围

对于 $20\%$ 的数据，$1 ≤ q, x_i ≤ 1000$。

对于 $40\%$ 的数据，$q = 1$，$1 ≤ x_i ≤ 10^{12}$。

对于 $60\%$ 的数据，$1 ≤ q ≤ 5000$，$1 ≤ x_i ≤ 10^{12}$。

对于另 $20\%$ 的数据，$1 ≤ q ≤ 10^5$，$1 ≤ x_i ≤ 10^6$。

对于 $100\%$ 的数据，满足 $1 ≤ q ≤ 2 × 10^5$，$1 ≤ x_i ≤ 10^{12}$，$x_i ≥ x_{i−1}$。

b_1.in  b_1.out

b_2.in  b_2.out

b_3.in  b_3.out