题目描述

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

为了彻底帮小可可弄懂这个问题， 你需要回答 q 组询问，对于每个 xi ，输出 。 其中， ⌊x⌋ 表示不大于 x 的最大整数。

输入格式

第一行一个正整数 q。

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

输出格式

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

样例****1​输入

2
5
10

样例****1​输出

5
13

样例****1​解释

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

数据规模与约定

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

对于 40% 的数据，q = 1，1 ≤ x ≤ 1012。

对于 60% 的数据，1 ≤ q ≤ 5000，1 ≤ x ≤ 10^12。

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

对于 100% 的数据，满足 1 ≤ q ≤ 2 × 10^5 ，1 ≤ xi ≤ 10^12 ，xi ≥ xi- 1。