AT_abc243_g [ABC243G] Sqrt

题目描述

有一个长度为 $1$ 的数列 $A=(X)$。对这个数列进行 $10^{100}$ 次如下操作。

操作：设 $A$ 的末尾元素为 $Y$。可以自由选择一个 $1$ 到 $\sqrt{Y}$ 之间的整数，并将其添加到 $A$ 的末尾。

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

给定 $T$ 组测试数据，请分别输出每组的答案。

在题目给定的限制条件下，可以证明答案不会超过 $2^{63}$。

输入格式

输入以如下格式从标准输入读入。

$T$
$\rm case_1$
$\vdots$
$\rm case_T$

每组数据格式如下。

$X$

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。

输入输出样例 #1

输入 #1

4
16
1
123456789012
1000000000000000000

输出 #1

5
1
4555793983
23561347048791096

说明/提示

限制条件

• $1 \leq T \leq 20$
• $1 \leq X \leq 9 \times 10^{18}$
• 输入中的所有值均为整数。

样例解释 1

对于第 $1$ 组数据，操作后可能得到的数列有如下 $5$ 种：

• $(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)$

由 ChatGPT 4.1 翻译