Rikka with Geometric Sequence

Problem Description

A long time ago, Rikka was not good at math. Worrying about Rikka's grades, Yuta sets many interesting math problems for Rikka to help her improve her skills. Now, as Rikka makes more and more progress on math, more and more she feels the joy of solving math tasks. Today, Yuta is quite busy and has no time to seek for new problems for Rikka. Therefore, for the first time, Rikka tries to come up with a problem herself. Setting a problem is just like building blocks. The first step is to choose the bricks. Rikka selects the concepts of "geometric sequence" and "subsequence": Sequence $a_1, \dots, a_k$ is a geometric sequence if and only if for each index $i \in [2, n-1]$, the values in the sequence holds $a_{i}^2=a_{i-1} \times a_{i+1}$. Sequnce $b_1, \dots, b_t$ is a subsequence of $a_1, \dots, a_k$ if and only if there exists an index sequence $c_1, \dots, c_t(1 \leq c_i \leq k)$ which satisfies $c_i < c_{i+1}$ for each $i \in [1,n)$ and $a_{c_i} = b_i$ for each $i \in [1,n]$. The second step is to combine the bricks. It is quite simple for Rikka: she soon finds an interesting problem: Given a positive integer $n$, count the number of different geometric subsequences of $1, 2, \dots, n$. The last step, and also the most important step, is to solve the problem. However, this task seems to be too difficult for Rikka. Therefore she seeks for help from you: Could you please help her solve this interesting math problem?

Input

The first line of the input contains a single integer $T(1 \leq T \leq 1000)$. For each test case, the input contains a single line with a single integer $n(1 \leq n \leq 5 \times 10^{17})$. The input guarantees that there are no more than $3$ test cases with $n > 10^9$.

Output

For each test case, output a single line with a single integer, the answer. The answer can be very large, you only need to print the answer modulo $998244353$. Hint When $n=4$, the valid subsequences are $\{1\},\{2\},\{3\},\{4\},\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\},\{1,2,4\}$. Therefore the answer is $11$.

Sample Input

10

1

2

3

4

5

6

7

8

9

100

Sample Output

1

3

6

11

16

22

29

39

50

5187

Source

2019 Multi-University Training Contest 9