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

为了彻底帮小可可弄懂这个问题，你需要回答 q 组询问，对于每个 x_i，输出

\sum_{j=1}^{x_i} ⌊j^{\frac{1}{3}}⌋

其中，⌊x⌋ 表示不大于 x 的最大整数。

第一行一个正整数 q。

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

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

样例 1 解释

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

数据规模与约定

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

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

对于 60% 的数据，1 ≤ q ≤ 5000，1 ≤ x ≤ 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}。