开方

题目描述

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

操作:设 $Y$ 为 $A$ 末尾的元素。选择 $1$ 到 $\sqrt{Y}$ 之间(含两端)的一个整数,并追加到 $A$ 的末尾。

求经过 $10^{100}$ 次操作后,可能得到多少种序列?

你需要回答 $T$ 组测试用例。

可以证明,在本问题的约束下,答案小于 $2^{63}$。

输入格式

输入按以下格式从标准输入给出:

T
case_1
⋮
case_T

每个用例按以下格式给出:

X

输出格式

输出 $T$ 行。第 $i$ 行输出 $\rm case_i$ 的答案。

样例

4
16
1
123456789012
1000000000000000000

5
1
4555793983
23561347048791096

在第一个用例中,可以通过操作得到以下五种序列。

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

数据范围

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