该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
从一个正整数 n 开始，每一步中，我们从 n 中减去不超过 n 的最大完全立方数，直到 n 变成零。
例如，n=100 时，该过程以 4 个步骤结束：
$$100 \xrightarrow{-4^3} 36 \xrightarrow{-3^3} 9 \xrightarrow{-2^3} 1 \xrightarrow{-1^3} 0.
$$
设 D(n) 表示该过程的步骤数，因此 D(100)=4.
设 S(N) 为所有严格小于 N 的正整数 n 对应的 D(n) 之和，因此 S(100)=512.
给定 n，求 S(n).
T 组询问。
Constraints and Subtasks
本题共 20 个测试点，各测试点等分。
对于全部测试点，满足：
- n≤1017
- T≤10000
其中，部分测试点有特殊性质：
- 测试点 1∼3 满足 n≤4×106；
- 测试点 4∼7 满足 n≤2×109。
| 测试点 |
数据范围 |
| 1∼3 |
n≤4×106,T≤10000 |
| 4∼8 |
n≤2×109,T≤10000 |
| 9∼20 |
n≤1017,T≤10000 |
输入内容从标准输入给出，格式如下：
$
\boxed{\begin{aligned}
{\quad} & n_1 {\quad} \\
& n_2 \\
& ~ \vdots \\
& n_T
\end{aligned}}
$
Output
输出 T 行，第 i(i=1,2,⋯,T) 行表示第 i 组询问的答案。
Samples
100
1000
512
6432
