#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace { using Integer = long long; //__int128; template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const vector& vec){for(int i=0; i ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template void print(const H& head){ cout << head; } template void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); } template void println(const T& ... values){ print(values...); cout << endl; } template void eprint(const H& head){ cerr << head; } template void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); } template void eprintln(const T& ... values){ eprint(values...); cerr << endl; } string operator "" _s (const char* str, size_t size){ return move(string(str)); } constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);} constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);} constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); } inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed mt19937 mt(chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()); template string join(const vector& v, const string& sep){ stringstream ss; for(int i=0; i0) ss << sep; ss << v[i]; } return ss.str(); } } constexpr long long mod = 9_ten + 7; namespace ExLucasTheorem{ // from uwicoder // http://www37.atwiki.jp/uwicoder/pages/2118.html#id_6779f709 long long C(long n, long r, int p, int q, vector& fact, vector& ifact, vector>& mod9) { if(n < 0 || r < 0 || r > n)return 0; int P = 9; long long z = n - r; int e0 = 0; for(long long u = n/p;u > 0;u /= p)e0 += u; for(long long u = r/p;u > 0;u /= p)e0 -= u; for(long long u = z/p;u > 0;u /= p)e0 -= u; int em = 0; for(long long u = n/P;u > 0;u /= p)em += u; for(long long u = r/P;u > 0;u /= p)em -= u; for(long long u = z/P;u > 0;u /= p)em -= u; long long ret = 1; while(n > 0){ //ret = ret * fact[n%P] % P * ifact[r%P] % P * ifact[z%P] % P; ret = mod9[ mod9[ mod9[ret][fact[ n%9 ]] ][ ifact[r%P] ] ][ ifact[z%P] ]; n /= p; r /= p; z /= p; } for(int i = 0;i < e0;++i)ret = mod9[ret][p]; if(!(p == 2 && q >= 3) && (em&1)==1)ret = (P-ret) % P; return ret; } vector> makeFF(int p, int q) { int P = 1; for(int i = 0;i < q;++i)P*=p; vector fact(P+1); vector ifact(P+1); fact[0] = 1; for(int i = 1;i <= P;++i){ if(i % p == 0){ fact[i] = fact[i-1]; }else{ fact[i] = fact[i-1] * i % P; } } for(int i = 0;i <= P;++i){ long long ret = 1; long long mul = fact[i]; for(long long n = P/p*(p-1)-1;n > 0;n >>= 1){ if((n&1)==1){ ret = (ret * mul) % P; } mul = (mul * mul) % P; } ifact[i] = (int)ret; } return vector>{fact, ifact}; } } int main_(){ int t; cin >> t; //vector> f = ExLucasTheorem::makeFF(3,2); vector> f = { {1,1,2,2,8,4,4,1,8,8}, {1,1,5,5,8,7,7,1,8,8} }; vector> mult(10, vector(10, 0)); for(int i=0; i<10; i++){ for(int j=0; j<10; j++){ mult[i][j] = i*j%9; } } vector memo(7_ten+10); while(t--){ long long n,r,x,a,b,m; scanf("%lld%lld%lld%lld%lld", &n,&r,&a,&b,&m); auto s = [&r,n,x,a,b,m](){ int ret = r; r = ((r^a)+b) % m; return ret%10; }; bool zero = true; long long ans = 0; for(int i=0; i=9) ans -= 9; } if(ans == 0 && !zero) ans = 9; printf("%lld\n", ans); } return 0; } template void get_process_time(T (*func)(Args...), const Args& ... a){ auto start_time = chrono::steady_clock::now(); func(a...); auto end_time = chrono::steady_clock::now(); eprintln("executed in", chrono::duration_cast(end_time-start_time).count(), " [ms]"); } int main(){ get_process_time(main_); return 0; }