题目背景

（Update on 2024/4/22 12:20）特别提示 #1：本题已经添加了两组针对 jsisonx 和 woscxk 的题解（1，2）的 hack 数据。请不要尝试使用时间复杂度为 $\bm {O(q\sqrt[3]{x})}$ 的算法通过此题。

（Update on 2024/4/22 18:26）特别提示 #2：请不要使用 (int) cbrt(x) 或 (int) pow(x, 1.0 / 3) 计算 $\bm {\lfloor \sqrt[3]{x} \rfloor}$ 的值。由于精度误差，计算出的值可能比真实值多 $\bm 1$ 或少 $\bm 1$。一个典型的例子在这里。对于评测分数为 $\bm{70}$ 分且 WA on #6，#8，#10 的代码，请特别注意。

（Update on 2024/4/24 19:58）特别提示 #3：对于使用 (int) cbrt(x) 和 (int) pow(x, 1.0 / 3) 导致的 WA，一种简便的补救方法是：将其改为 (int) cbrt(x + 0.5) 和 (int) pow(x + 0.5, 1.0 / 3)。

题目描述

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

为了彻底帮小可可弄懂这个问题，你需要回答 $q$ 组询问，对于每组询问给定的一个正整数 $x_i$，输出：

$$\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor $$

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

输入格式

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

接下来 $q$ 行，第 $i$ 行一个正整数 $x_i$。

保证给出的 $\bm{x_1 \sim x_q}$ 单调不降。

输出格式

$q$ 行，每行一个正整数，表示该组询问的答案。

请注意答案的范围。

2
5
10

5
13

提示

样例 1 解释

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

数据范围

对于 $20\%$ 的数据，$x_q,q \le 1000$。

对于另外 $20\%$ 的数据，$q=1$。

对于另外 $20\%$ 的数据，$q \le 5000$。

对于另外 $20\%$ 的数据，$q \le 10^5$，$x_q \le 10^6$。

对于 $100\%$ 的数据，$1 \le q \le 2 \times 10^5$，$1 \le x_1 \le x_2 \le \ldots \le x_q \le 10^{12}$。