8095 | naoya_t | PALIN1 | C | Accepted | 58.7336/*//
/*/typedef long long l;l n,p,u=1<<30,c,d;l j(l x,l e){return--e?j(x*4%p,e):x;}l m(l a,l b){c=a%u,a/=u,d=b%u,b/=u;return(j(a*b%p,31)+j((a*d+b*c)%p,16)+c*d%p)%p;}l f(l a,l b){return b?b&1?m(a,f(a,b-1)):f(m(a,a),b/2):1;}main(t){scanf("%d",&t);while(t--)scanf("%lld%lld",&n,&p),printf("%lld\n",f(n,n));}//*//
/*/typedef long long l;l n,p,u=1<<30,c,d;l j(l x,l e){return--e?j(x*4%p,e):x;}l m(l a,l b){c=a%u,a/=u,d=b%u,b/=u;return(j(a*b%p,31)+j((a*d+b*c)%p,16)+c*d%p)%p;}l f(l a,l b){return b?b&1?m(a,f(a,b-1)):f(m(a,a),b/2):1;}main(t){scanf("%d",&t);while(t--)scanf("%lld%lld",&n,&p),printf("%lld\n",f(n,n));};;};))n,n(f,"n\dll%"(ftnirp,)p&,n&,"dll%dll%"(fnacs)--t(elihw;)t&,"d%"(fnacs{)t(niam};1:)2/b,)a,a(m(f:))1-b,a(f,a(m?1&b?b nruter{)b l,a l(f l};p%)p%d*c+)61,p%)c*b+d*a((j+)13,p%b*a(j(nruter;u=/b,u%b=d,u=/a,u%a=c{)b l,a l(m l};x:)e,p%4*x(j?e--nruter{)e l,x l(j l;d,c,03<<1=u,p,n l;l gnol gnol fedepyt/*/
//*//