Score : $600$ points

问题陈述

我们有一个长度为 $1$ 的序列：$A=(X)$。让我们对这个序列执行以下操作 $10^{100}$ 次。

操作：令 $Y$ 为 $A$ 尾部的元素。从 $1$ 到 $\sqrt{Y}$（包含）之间选择一个整数，并将其追加到 $A$ 的末尾。

经过 $10^{100}$ 次操作后，可以得到多少种不同的序列？

你将得到 $T$ 个测试用例需要解决。

在约束条件下，可以证明答案小于 $2^{63}$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a sequence of length $1$: $A=(X)$. Let us perform the following operation on this sequence $10^{100}$ times.

Operation: Let $Y$ be the element at the end of $A$. Choose an integer between $1$ and $\sqrt{Y}$ (inclusive), and append it to the end of $A$.

How many sequences are there that can result from $10^{100}$ operations?

You will be given $T$ test cases to solve.

It can be proved that the answer is less than $2^{63}$ under the Constraints.

Constraints

• $1 \leq T \leq 20$
• $1 \leq X \leq 9\times 10^{18}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$T$

$\rm case_1$

$\vdots$

$\rm case_T$

Each case is in the following format:

$X$

Output

Print $T$ lines. The $i$-th line should contain the answer for $\rm case_i$.

Sample Input 1

4
16
1
123456789012
1000000000000000000

Sample Output 1

5
1
4555793983
23561347048791096

In the first case, the following five sequences can result from the operations.

• $(16,4,2,1,1,1,\ldots)$
• $(16,4,1,1,1,1,\ldots)$
• $(16,3,1,1,1,1,\ldots)$
• $(16,2,1,1,1,1,\ldots)$
• $(16,1,1,1,1,1,\ldots)$

update @ 2024/3/10 10:27:55