题目描述

小可爱想计算所有不大于 $x$ 的正整数的立方根（$2^3=8$, $2$ 就是 $8$ 的立方根）向下取整之和，但是她不会做，你能帮帮她吗？

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

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

输入格式

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

输出格式

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

样例

输入

2
5
10

输出

5
13

解释

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}$。