Fansblog

/**
 *    author: Akvicor
 *    created: 2019-07-30 08-57-12
**/

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define per(i, a, n) for(int i = a; i >= n; --i)
#define prec(x) fixed << setprecision(x)
#define ms(s, n) memset(s, n, sizeof(s))
#define mod(x) ((x) %= MOD)
#define all(v) (v).begin(), (v).end()
#define sz(x) ((int)(x).size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define fi first
#define se second
#define MOD(x) const int MOD = (int)x
#define MAXN(x) const int MAXN = (int)x + 10

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<LL, LL> PLL;
typedef vector<LL> VL;
typedef vector<PLL> VLL;

namespace SOL{

const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;

/**  >------- Akvicor's Solution -------< **/

MOD(1e9+7);
MAXN(1e6);

const int S = 8;

LL mult_mod(LL a, LL b, LL c){
	a %= c;
	b %= c;
	LL ret = 0;
	LL tmp = a;
	while(b){
		if(b&1){
			ret += tmp;
			if(ret > c) ret -= c;
		}
		tmp <<= 1;
		if(tmp > c) tmp -= c;
		b >>= 1;
	}
	return ret;
}

LL pow_mod(LL a, LL n, LL mod){
	LL ret = 1;
	LL temp = a % mod;
	while(n){
		if(n & 1) ret = mult_mod(ret, temp, mod);
		temp = mult_mod(temp, temp, mod);
		n >>= 1;
	}
	return ret;
}

bool check(LL a, LL n, LL x, LL t){
	LL ret = pow_mod(a, x, n);
	LL last = ret;
	loop(i, 1, t){
		ret = mult_mod(ret, ret, n);
		if(ret == 1 && last != 1 && last != n-1) return true;
		last = ret;
	}
	if(ret != 1) return true;
	else return false;
}

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));
	rep(i, S){
		LL a = rand()%(n-1)+1;
		if(check(a, n, x, t)) return false;
	}
	return true;
}

void solve(){
    FAST_IO;
    
    int t;
	LL p;
	cin >> t;
	while(t--){
		cin >> p;
		LL ans = 1;
		for(LL i = p-1; i >= 0; --i){
			if(Miller_Rabin(i)) break;
			ans = mult_mod(ans, i, p);
		}
		ans = (p-pow_mod(ans, p-2, p)) % p;
		cout << ans << endl;
	}
    
}

/**  >----------------------------------< **/

}

int main(){

#ifdef DEBUG
    int DEBUGCNT = 0;
    clock_t DEBUGstart, DEBUGfinish;
    double DEBUGduration;
    cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
    while (DEBUGCNT < 70) {
        cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
        DEBUGstart = clock();
#endif

        SOL::solve();

#ifdef DEBUG
        DEBUGfinish = clock();
        DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
        cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
        if (cin.eof()) break;
        if (!cin.good()) break;
        if (cin.fail()) break;
        if (cin.bad()) break;
        ++DEBUGCNT;
    }
    cout << ">----------------------------------<" << endl << endl;
#endif

    return 0;
}