#include <bits/stdc++.h>#define LL long longusing namespace std;struct Maxtri{    LL v[2][2];    Maxtri(){memset(v,0,sizeof(v));}}ori;LL n, y, x, s, mod ;Maxtri mult(Maxtri a,Maxtri b){    Maxtri temp;    for(int i=0;i<2;i++){        for(int j=0;j<2;j++){            for(int k=0;k<2;k++){                temp.v[i][j] = (temp.v[i][j]+(a.v[i][k]*b.v[k][j])%mod)%mod;            }        }    }    return temp;}LL pow_mod(Maxtri a,LL n){    if(n==0) return 0;    if(n==1) return 1;    if(n==2) return 2;    n-=2;    Maxtri ans;    for(int i=0;i<2;i++){        ans.v[i][i] = 1;    }    while(n){        if(n&1) ans = mult(ans,a);        a = mult(a,a);        n>>=1;    }    return (ans.v[0][0]*2+ans.v[0][1])%mod;}LL pow_mod1(LL a,LL n,LL mod){    LL ans = 1;    while(n){        if(n&1) ans = ans*a%mod;        a = a*a%mod;        n>>=1;    }    return ans;}LL Phi(LL x){    LL ans = x;    for(LL i=2LL; i*i<=x; i++)    {        if(x % i == 0)        {            ans -= ans/i;            while(x % i == 0)                x /= i;        }    }    if(x > 1)        ans -= ans/x;    return ans;}int main(){    ori.v[0][0] = 2,ori.v[0][1] = 1;    ori.v[1][0] = 1,ori.v[1][1] = 0;    int tcase;    scanf("%d",&tcase);    while(tcase--){        scanf("%lld%lld%lld%lld",&n, &y, &x, &s);        s++;        LL phi = 2*Phi(s);        mod = 2*phi;        LL fn = pow_mod(ori,n*y);        LL fn1 = pow_mod(ori,n*y+1);        LL ans = ((fn*fn1)%mod/2);        ans+=phi;        printf("%lld\n",pow_mod1(x,ans,s)%s);    }    return 0;}