Candies for Friends

Limits: 4 sec., 1024 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka decided to invite their friends over after an exhausting Olympiad to their apartment and treat them to candies.

They have \(n\) algorithmic friends. Some of them are so dedicated that they do not stop solving problems neither day nor night, and will be writing the AtCoder Regular Contest today. They do not know the exact number of friends who plan to write this contest (and will not come to visit because of this). However, they know that there will be at least one such friend, but not more than \(k\). That is, \(n-1\), \(n-2\), ..., or \(n-k\) friends can accept Zenyk and Marichka’s invitation.

Zenyk and Marichka must make the best possible impression on their guests. They want to buy candies so that they can divide them equally among the friends, no matter how many of them gather. Note that they cannot keep some candies for themselves or distribute them unequally, as this would violate the rules of etiquette. Therefore, they will buy exactly \(\text{LCM}(n-1, n-2, \dots, n-k)\) candies.

After Zenyk and Marichka bought the candies, they noticed that they can divide this amount among all \(n\) friends.

Makeshift value of \(k\) is known to you, but you do not know the number of friends \(n\). Count how many such values of \(n\) satisfy the condition. Formally, you need to count the number of natural numbers \(n > k\) such that \(\text{LCM}(n-1, n-2, \dots, n-k)\) is divisible by \(n\). Since this count can be very large, you should calculate the remainder of its division by the prime number 998244353.

Zenyk and Marichka want everything to go perfectly, so they consider \(t\) different values of \(k\), for each of which they ask you to solve the problem independently.

Input

The first line contains a single integer \(t\) — the number of queries.

The next line contains \(t\) integers \(k\), for each of which you need to solve the problem.

Output

In a single line, output \(t\) integers — the answers to the corresponding queries, that is, the number of integers \(n\) for which \(\text{LCM}(n-1, n-2, \dots, n-k)\) is divisible by \(n\) modulo 998244353.

Constraints

\(1 \le t \le 10^5\),

\(1 \le k \le 10^7\).

Problem evaluation consists of the following subtasks:

1 point — sample from the statement,

4 points — \(t = 1, k \le 20\),

10 points — \(t = 1, k \le 10^7\),

10 points — without additional constraints.

Points for a subtask will be awarded only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 4 101	2 322961306

Notes

\(\text{LCM}(n-1, n-2, \dots, n-k)\) is the least common multiple, i.e., the smallest natural number that is divisible by \(n-1, n-2, \dots, n-k\).

For \(k=4\), the condition is satisfied by \(n=6\) and \(n=12\).

• \(\text{LCM}(5, 4, 3, 2) = 60\) is divisible by 6.

• \(\text{LCM}(11, 10, 9, 8) = 3960\) is divisible by 12.

For \(k=101\), the answer is \(322961306 \equiv 1321205659\pmod{998244353}\).