题目描述

对于一个质数 $n$，如果一个正整数对 $(x,y)$ 满足以下条件： $$ x^y\equiv y^x \pmod n $$ 则我们称这样的一对 $(x,y)$ 是有魔法的。

给定 $n$，请计算 $0 < x,y \le n(n-1)$ 中有多少对有魔法的有序对。答案对 $998244353$ 取模。

输入格式

第一行给出正整数 $T$ 表示数据组数。

接下来 $T$ 行每行一个质数 $n$。

输出格式

输出 $T$ 行，每行一个整数表示答案。

样例

样例输入

5
5
11
67
97
101

样例输出

104
1550
479886
1614336
1649000

数据范围与约定

$1\le T\le 10, 2\le n\le 10^{18}$。保证 $n$ 是质数，且 $n-1$ 不是 $998244353$ 的倍数。

对于 $10\%$ 的数据，$n\le 100$。

对于 $30\%$ 的数据，$n\le 10^9$。