题目描述

问题陈述

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

操作：设 $Y$ 是 $A$ 的最后一个元素。选择一个介于 $1$ 和 $\\sqrt{Y}$（包括边界）之间的整数，并将其附加到 $A$ 的末尾。

经过 $10^{100}$ 次操作后，有多少个不同的序列可以生成？

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

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

约束条件

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

输入

从标准输入读入数据，输入格式如下：

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

每个测试用例的格式如下：

$X$

输出

打印 $T$ 行。第 $i$ 行应该包含 $\\rm case_i$ 的答案。

示例输入1

4
16
1
123456789012
1000000000000000000

示例输出1

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