题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6608
题目大意： 给 你 一 个 1 0 9 − 1 0 14 给你一个10^9 - 10^{14} 给你一个109−1014内的质数p，求小于p的最大质数的阶乘取模p。

#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;
long long gcd(long long a,long long b) {
    if (b == 0) return a;
    return gcd(b,a%b);
}
long long mul(long long a,long long b,long long mod){
    long long ret=0;
    while(b) {
        if(b & 1) ret=(ret+a)%mod;
        a=(a+a)%mod;
        b >>= 1;
    }
    return ret;
}
long long pow(long long a,long long b,long long mod) {
    long long ret = 1;
    while(b) {
        if(b & 1) ret = mul(ret,a,mod);
        a = mul(a,a,mod);
        b >>= 1;
    }
    return ret;
}
bool check(long long a,long long n){
    long long x = n - 1;
    int t = 0;
    while((x & 1) == 0) {
        x >>= 1;
        t ++;
    }
    x = pow(a,x,n);
    long long y;
    for(int i=1;i<=t;i++) {
        y = mul(x,x,n);
        if(y == 1 && x != 1 && x != n - 1) return true;
        x = y;
    }
    if(y != 1) return true;
    return false;
}
bool Miller_Rabin(long long n) {
    if(n == 2) return true;
    if(n == 1 || !(n & 1)) return false;
    const int arr[12] = {2,3,5,7,11,13,17,19,23,29,31,37};
    for(int i = 0; i < 12; i++) {
        if (arr[i] >= n) break;
        if(check(arr[i], n)) return false;
    }
    return true;
}

int main() {
    int t;long long n;scanf("%d",&t);
    while(t--) {
        scanf("%lld",&n);long long p=n-1;
        while(!Miller_Rabin(p)) p--;
        long long ans=1;
        for(long long i=p+1;i+1<n;i++) ans=mul(ans,pow(i,n-2,n),n);
        printf("%lld\n",ans);
    }
}