← 返回题目列表

AtCoder · abc243_g

G. 平方根

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个长度为 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)