F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Rikka with Geometric Sequence

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 189    Accepted Submission(s): 79

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

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-08-14 19:36:22, Gzip enabled Administration