E. Magical Pair
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

For a prime number $$$n$$$, if a pair of positive integers $$$(x, y)$$$ satisfies the congruence relation: $$$$$$x^y\equiv y^x \pmod n.$$$$$$ Then we consider $$$(x, y)$$$ to be magical.

We want to know how many ordered pairs of positive integers $$$(x, y)$$$ are magical for a given prime number $$$n$$$, where $$$0 \lt x, y \le n^2 - n$$$. Since the answer could be large, we will output it modulo 998244353.

Input

The first line input a positive integer $$$T$$$ $$$(1\le T \le 10)$$$, which represents the total number of test cases.

Then for each test case, input a single line with a prime number $$$n$$$ $$$(2\le n \le 10^{18})$$$, and it's guaranteed that $$$n-1$$$ is not a multiple of $$$998244353$$$.

Output

Output $$$T$$$ lines, each containing an integer representing the result modulo $$$998244353$$$.

Examples
Input
5
5
11
67
97
101
Output
104
1550
479886
1614336
1649000
Input
6
998244353
998244853
19260817
1000000007
1000000009
350979772330483783
Output
284789646
90061579
971585925
887008006
527110672
334479293