Background

The testdata for this problem is not official.

We are collecting official testdata (that can be uploaded here).

Official testdata (cannot be uploaded here): https://www.luogu.com.cn/training/499869

Unofficial testdata download: https://scg3.piaoztsdy.cn/training/69bce235a7cf509104565c83

Special notes:

1. Please use (int) cbrt(x + 0.5) to compute $\lfloor \sqrt[3]{x} \rfloor$, otherwise precision errors may occur.
2. This problem includes two hack test cases against algorithms with time complexity $O(q\sqrt[3]{x})$ (#11 and #12).

Problem Description

Xiaokeke wants to compute the sum of the floored cube roots of all positive integers not greater than $x$, but she does not know how. Can you help her?

To fully help Xiaokeke understand this problem, you need to answer $q$ queries. For each query, given a positive integer $x_i$, output:

$$\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor$$

Here, $\lfloor x \rfloor$ denotes the greatest integer not greater than $x$.

Input Format

The first line contains a positive integer $q$.

Then follow $q$ lines. The $i$-th line contains a positive integer $x_i$.

It is guaranteed that $\bm{x_1 \sim x_q}$ is non-decreasing.

Output Format

Output $q$ lines. Each line contains a positive integer, representing the answer to that query.

Please pay attention to the range of the answer.

2
5
10

5
13

Hint

Sample 1 Explanation

The floored cube roots of $1 \sim 10$ are: $1,1,1,1,1,1,1,2,2,2$.

Constraints

For $20\%$ of the data, $x_q,q \le 1000$.

For another $20\%$ of the data, $q=1$.

For another $20\%$ of the data, $q \le 5000$.

For another $20\%$ of the data, $q \le 10^5$, $x_q \le 10^6$.

For $100\%$ of the data, $1 \le q \le 2 \times 10^5$, $1 \le x_1 \le x_2 \le \ldots \le x_q \le 10^{12}$.

Translated by ChatGPT 5