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

# Do You Like Interactive Problems?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 274    Accepted Submission(s): 149

Problem Description
There is an integer $x$ satisfying $1\le x\le n$. You know $n$ but you don't know $x$.

You can do the following guessing: pick an random integer $y$ uniformly satisfying $1\le y\le n$ (your $y$ may equal to previous queries), and you will be told if $x< y$, $x> y$ or $x=y$. You will stop asking if there is only one possible $x$ satisfying all the conditions.

Given $n$, if $x$ is picked randomly uniformly, what's your expected number of queries?

Input
The first line contains an integer $T$ ($1\le T\le 100$) denoting the number of test cases.

For each test case, the only line contains an integer $n$ ($1\le n\le 10^9$).

Output
For each test case, output one integer denoting the expected number of queries modulo $998244353$.

Formally, it can be proven that the sought expected value can be represented as an irreducible fraction $p/q$ which satisfies $q\not\equiv 0\bmod{998244353}$, and there is a unique integer $r$ satisfies $0\le r<998244353$ and $qr\equiv p\bmod{998244353}$. Find this $r$.

Sample Input
2
1
2

Sample Output
0
1

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-06-17 03:35:46, Gzip enabled Administration