#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c=getchar(); x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) {x=x*+c-''; c=getchar();}

}

LL MOD;

struct Matrix

{

    long long A[][];

    int R, C;

    Matrix operator*(Matrix b);

};

Matrix X, Y, Z;

Matrix Matrix::operator*(Matrix b)

{

    Matrix c;

    memset(c.A, , sizeof(c.A));

    int i, j, k;

    for (i = ; i <= R; i++)

        for (j = ; j <= b.C; j++)

            for (k = ; k <= C; k++)

                c.A[i][j] = (c.A[i][j] + (A[i][k] * b.A[k][j]) % MOD) % MOD;

    c.R = R; c.C = b.C;

    return c;

}

void init()

{

    memset(X.A, , sizeof X.A);

    memset(Y.A, , sizeof Y.A);

    memset(Z.A, , sizeof Z.A);

    Y.R = ; Y.C = ;

    for (int i = ; i <= ; i++) Y.A[i][i] = ;

    X.R = ; X.C = ;

    X.A[][]=-;

    X.A[][]=; X.A[][]=;

    X.A[][]=; X.A[][]=;

    Z.R = ; Z.C = ;

    Z.A[][]=; Z.A[][]=; Z.A[][]=;

}

LL work(LL tt)

{

    if(tt==) return ;

    if(tt==) return ;

    if(tt==) return ;

    tt=tt-; init();

    while (tt)

    {

        if (tt %  == ) Y = Y*X;

        tt = tt >> ;

        X = X*X;

    }

    Z = Z*Y;

    return Z.A[][];

}

int T;

LL n,x,y,s;

LL phi(LL x)

{

     LL res=x,a=x;

     for(int i=;i*i<=a;i++)

     {

         if(a%i==)

         {

             res=res/i*(i-);

             while(a%i==) a/=i;

         }

     }

     if(a>) res=res/a*(a-);

     return res;

}

LL pow(LL a,LL b,LL mod)

{

    LL c=;

    while(b!=)

    {

        if(b%==) c=(c*a)%mod,b--;

        else a=(a*a)%mod,b=b/;

    }

    return c;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

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

        MOD=phi(s+);

        LL gn=work(n*y)+MOD;

        LL ans=pow(x,gn,s+);

        printf("%lld\n",ans);

    }

    return ;

}