Fansblog

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-07-30 08-57-12
  4**/
  5
  6#include <bits/stdc++.h>
  7
  8using namespace std;
  9
 10#ifdef DEBUG
 11#define FAST_IO 17
 12#else
 13#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 14#define endl '\n'
 15#endif
 16
 17#define rep(i, n) for(int i = 0; i < (n); ++i)
 18#define reep(i, n) for(int i = 0; i <= (n); ++i)
 19#define lop(i, a, n) for(int i = a; i < (n); ++i)
 20#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 21#define per(i, a, n) for(int i = a; i >= n; --i)
 22#define prec(x) fixed << setprecision(x)
 23#define ms(s, n) memset(s, n, sizeof(s))
 24#define mod(x) ((x) %= MOD)
 25#define all(v) (v).begin(), (v).end()
 26#define sz(x) ((int)(x).size())
 27#define mp(x, y) make_pair(x, y)
 28#define pb(x) push_back(x)
 29#define fi first
 30#define se second
 31#define MOD(x) const int MOD = (int)x
 32#define MAXN(x) const int MAXN = (int)x + 10
 33
 34typedef long long LL;
 35typedef unsigned long long ULL;
 36typedef pair<int, int> PII;
 37typedef vector<int> VI;
 38typedef vector<PII> VII;
 39typedef pair<LL, LL> PLL;
 40typedef vector<LL> VL;
 41typedef vector<PLL> VLL;
 42
 43namespace SOL{
 44
 45const double EPS = 1e-6;
 46const double PI = acos(-1.0);
 47const int INF = 0x3f3f3f3f;
 48const LL LINF = 0x7f7f7f7f7f7f7f7f;
 49
 50/**  >------- Akvicor's Solution -------< **/
 51
 52MOD(1e9+7);
 53MAXN(1e6);
 54
 55const int S = 8;
 56
 57LL mult_mod(LL a, LL b, LL c){
 58	a %= c;
 59	b %= c;
 60	LL ret = 0;
 61	LL tmp = a;
 62	while(b){
 63		if(b&1){
 64			ret += tmp;
 65			if(ret > c) ret -= c;
 66		}
 67		tmp <<= 1;
 68		if(tmp > c) tmp -= c;
 69		b >>= 1;
 70	}
 71	return ret;
 72}
 73
 74LL pow_mod(LL a, LL n, LL mod){
 75	LL ret = 1;
 76	LL temp = a % mod;
 77	while(n){
 78		if(n & 1) ret = mult_mod(ret, temp, mod);
 79		temp = mult_mod(temp, temp, mod);
 80		n >>= 1;
 81	}
 82	return ret;
 83}
 84
 85bool check(LL a, LL n, LL x, LL t){
 86	LL ret = pow_mod(a, x, n);
 87	LL last = ret;
 88	loop(i, 1, t){
 89		ret = mult_mod(ret, ret, n);
 90		if(ret == 1 && last != 1 && last != n-1) return true;
 91		last = ret;
 92	}
 93	if(ret != 1) return true;
 94	else return false;
 95}
 96
 97bool Miller_Rabin(LL n){
 98	if(n < 2) return false;
 99	if(n == 2) return true;
100	if((n&1)==0) return false;
101	LL x = n-1;
102	LL t = 0;
103	while((x&1)==0){x >>= 1; ++t;}
104	srand(time(NULL));
105	rep(i, S){
106		LL a = rand()%(n-1)+1;
107		if(check(a, n, x, t)) return false;
108	}
109	return true;
110}
111
112void solve(){
113    FAST_IO;
114    
115    int t;
116	LL p;
117	cin >> t;
118	while(t--){
119		cin >> p;
120		LL ans = 1;
121		for(LL i = p-1; i >= 0; --i){
122			if(Miller_Rabin(i)) break;
123			ans = mult_mod(ans, i, p);
124		}
125		ans = (p-pow_mod(ans, p-2, p)) % p;
126		cout << ans << endl;
127	}
128    
129}
130
131/**  >----------------------------------< **/
132
133}
134
135int main(){
136
137#ifdef DEBUG
138    int DEBUGCNT = 0;
139    clock_t DEBUGstart, DEBUGfinish;
140    double DEBUGduration;
141    cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
142    while (DEBUGCNT < 70) {
143        cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
144        DEBUGstart = clock();
145#endif
146
147        SOL::solve();
148
149#ifdef DEBUG
150        DEBUGfinish = clock();
151        DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
152        cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
153        if (cin.eof()) break;
154        if (!cin.good()) break;
155        if (cin.fail()) break;
156        if (cin.bad()) break;
157        ++DEBUGCNT;
158    }
159    cout << ">----------------------------------<" << endl << endl;
160#endif
161
162    return 0;
163}