Magical Pair
Description
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 < x, y \le n^2 - n$. Since the answer could be large, we will output it modulo 998244353.
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 $T$ lines, each containing an integer representing the result 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$.
5
5
11
67
97
101
6
998244353
998244853
19260817
1000000007
1000000009
350979772330483783
104
1550
479886
1614336
1649000
284789646
90061579
971585925
887008006
527110672
334479293