#include #include #include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=(x-x);x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) string S; ll mo; ll N; ll T; ll mul(ll x,ll y) { ll r=x-x,a=x==x; while(y) { if(y&a) r+=x; x<<=a; y>>=a; } return r; } ll momo(ll v) { lldiv_t d; d=div(v,mo); return d.rem; } ll fib(ll k,ll a,ll b) { int z=k-k; a=k==k; b=a+a+a; int c=a+a; if(k==a) return a; if(k==a+a) return b; k-=a+a; vector V; V.push_back(z); V.push_back(z); vector> R,A; R.push_back(V); R.push_back(V); A.push_back(V); A.push_back(V); R[z][z]=a; R[z][a]=z; R[a][z]=z; R[a][a]=a; A[z][z]=a; A[z][a]=a; A[a][z]=a; A[a][a]=z; while(k) { if(k&a) { vector> S; S.push_back(V); S.push_back(V); S[z][z]=momo(mul(A[z][z],R[z][z])+mul(A[z][a],R[a][z])); S[z][a]=momo(mul(A[z][z],R[z][a])+mul(A[z][a],R[a][a])); S[a][z]=momo(mul(A[a][z],R[z][z])+mul(A[a][a],R[a][z])); S[a][a]=momo(mul(A[a][z],R[z][a])+mul(A[a][a],R[a][a])); swap(S,R); } vector> T; T.push_back(V); T.push_back(V); T[z][z]=momo(mul(A[z][z],A[z][z])+mul(A[z][a],A[a][z])); T[z][a]=momo(mul(A[z][z],A[z][a])+mul(A[z][a],A[a][a])); T[a][z]=momo(mul(A[a][z],A[z][z])+mul(A[a][a],A[a][z])); T[a][a]=momo(mul(A[a][z],A[z][a])+mul(A[a][a],A[a][a])); swap(T,A); k>>=a; } return momo(mul(b,R[z][z])+R[z][a]); } void solve() { int i,j,k,l,r,x,y; string s; char c=x-x; c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++; c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++; c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++;c++; c++; S.push_back(c); c--; S.push_back(c); S.push_back(c); S.push_back(c); S.push_back(c); S.push_back(c); S.push_back(c); S.push_back(c); S.push_back(c); c++;c++;c++;c++;c++;c++;c++; S.push_back(c); mo=atoi(S.c_str()); cin>>T; while(T--) { cin>>N; cout<