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)