#include <bits/stdc++.h>

#define LL long long

using namespace std;

struct Maxtri{

    LL v[][];

    Maxtri(){memset(v,,sizeof(v));}

}ori;

LL n, y, x, s, mod ;

Maxtri mult(Maxtri a,Maxtri b){

    Maxtri temp;

    for(int i=;i<;i++){

        for(int j=;j<;j++){

            for(int k=;k<;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==) return ;

    if(n==) return ;

    if(n==) return ;

    n-=;

    Maxtri ans;

    for(int i=;i<;i++){

        ans.v[i][i] = ;

    }

    while(n){

        if(n&) ans = mult(ans,a);

        a = mult(a,a);

        n>>=;

    }

    return (ans.v[][]*+ans.v[][])%mod;

}

LL pow_mod1(LL a,LL n,LL mod){

    LL ans = ;

    while(n){

        if(n&) ans = ans*a%mod;

        a = a*a%mod;

        n>>=;

    }

    return ans;

}

LL Phi(LL x)

{

    LL ans = x;

    for(LL i=2LL; i*i<=x; i++)

    {

        if(x % i == )

        {

            ans -= ans/i;

            while(x % i == )

                x /= i;

        }

    }

    if(x > )

        ans -= ans/x;

    return ans;

}

int main(){

    ori.v[][] = ,ori.v[][] = ;

    ori.v[][] = ,ori.v[][] = ;

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        scanf("%lld%lld%lld%lld",&n, &y, &x, &s);

        s++;

        LL phi = *Phi(s);

        mod = *phi;

        LL fn = pow_mod(ori,n*y);

        LL fn1 = pow_mod(ori,n*y+);

        LL ans = ((fn*fn1)%mod/);

        ans+=phi;

        printf("%lld\n",pow_mod1(x,ans,s)%s);

    }

    return ;

}