1711 - 【入门】立方根

通过次数

0

提交次数

7

Time Limit : 1 秒
Memory Limit : 128 MB

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

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

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

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

Input

第一行一个正整数 q

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

Output

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

Examples

Input

2
5
10

Output

5
13

Hint

样例 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}