威爾遜定理 當且僅當p為素數,p | (p-1)!+1

若p為合數,則p=a*b;如果a!=b,那么p|(p-1)!,
如果a=b,如果p為4,那么p|(p-1)!=2,如果p大于4,那么sqrt§和sqrt(2q)肯定屬于(p-1)!中,可以整除

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>
#include<ctime>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;ll mult(ll a, ll b, ll p) {a %= p;b %= p;ll res = 0, tmp = a;while(b) {if (b & 1) {res += tmp;if (res > p) res -= p;}tmp <<= 1;if (tmp > p) tmp -= p;b >>= 1;}return res;
}ll quick_pow(ll a, ll b, ll p) {ll res = 1;ll tmp = a % p;while(b) {if (b & 1) res = mult(res, tmp, p);tmp = mult(tmp, tmp, p);b >>= 1;}return res;
}bool check(ll a, ll n, ll x, ll t) {ll res = quick_pow(a, x, n);ll last = res;for (ll i = 1; i <= t; i++) {res = mult(res, res, n);if (res == 1 && last != 1 && last != n-1) return true;last = res;}return res != 1;
}bool Miller_Rabin(ll n) {if (n < 2) return false;if (n == 2) return true;if ((n & 1) == 0) return false;ll x = n-1;ll t = 0;while ((x & 1) == 0) {x >>= 1;t++;}srand(time(NULL));const ll tims = 8;for (ll i = 0; i < tims; i++) {ll a = rand() % (n-1) + 1;if (check(a, n, x, t)) return false;}return true;
}int main()
{int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);if(n==4){printf("2\n");}else if(Miller_Rabin(n)){printf("%d\n",n-1);}else{printf("0\n");}}return 0;
}