G - Sqrt Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ 1 の数列 A=(X) があります。この数列に対して次の操作を 10^{100} 回行います。

操作：A の末尾の要素を Y とする。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

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)

Score : 600 points

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)