对于一个素数 $n$，如果一对正整数 $(x, y)$ 满足同余关系： $$x^y \equiv y^x \pmod n$$ 则称 $(x, y)$ 为“神奇的”。

给定一个素数 $n$，我们想要知道有多少对有序正整数 $(x, y)$ 是神奇的，其中 $0 < x, y \le n^2 - n$。由于答案可能很大，请输出其对 $998244353$ 取模的结果。

输入格式

第一行输入一个正整数 $T$ ($1 \le T \le 10$)，表示测试用例的总数。 对于每个测试用例，输入一行包含一个素数 $n$ ($2 \le n \le 10^{18}$)，且保证 $n - 1$ 不是 $998244353$ 的倍数。

输出格式

输出 $T$ 行，每行包含一个整数，表示结果对 $998244353$ 取模后的值。

样例

样例输入 1

5
5
11
67
97
101

样例输出 1

104
1550
479886
1614336
1649000

样例输入 2

6
998244353
998244853
19260817
1000000007
1000000009
350979772330483783

样例输出 2

284789646
90061579
971585925
887008006
527110672
334479293