#include<cstdio>

typedef long long LL;



LL pw(LL x,LL p,LL mod){LL ans=1;for(;p;p>>=1){if(p&1)ans=ans*x%mod;x=x*x%mod;}return ans;}
LL ni(LL x,LL mod){return pw(x,mod-2,mod);}

struct Matrix{
    int n,m,mod;
    LL data[4][4];
    Matrix(){}
    Matrix(int _n,int _m,int _mod){n=_n,m=_m,mod=_mod;}
    Matrix operator*(Matrix m2){
        Matrix tmp(n,m2.m,mod);
        for(int i=0;i!=n;++i)
            for(int j=0;j!=m2.m;++j){
                tmp.data[i][j]=0;
                for(int k=0;k!=m;++k)
                    tmp.data[i][j]=(tmp.data[i][j]+data[i][k]*m2.data[k][j])%mod;
            }
        return tmp;
    }
};
Matrix I(int n,int mod){
    Matrix tmp(n,n,mod);
    for(int i=0;i!=n;++i)
        for(int j=0;j!=n;++j)
            if(i==j)tmp.data[i][j]=1; else tmp.data[i][j]=0;
    return tmp;
}

int main(){
    int _; scanf("%d",&_);
    while(_--){
        LL n; int a,b,c,p; scanf("%I64d%d%d%d%d",&n,&a,&b,&c,&p);
        LL x=pw(a,b,p);
        Matrix v=I(4,p-1),q(4,4,p-1);
        for(int i=0;i!=4;++i)
            for(int j=0;j!=4;++j)q.data[i][j]=0;
        q.data[0][0]=q.data[2][1]=q.data[3][2]=q.data[0][3]=q.data[2][3]=1;
        q.data[3][3]=c;
        --n;
        while(n){
            if(n&1)v=v*q;
            q=q*q; n>>=1;
        }
        Matrix vec(1,4,p-1);
        vec.data[0][0]=1; vec.data[0][1]=0; vec.data[0][2]=1; vec.data[0][3]=c+1;
        vec=vec*v;
        LL pq=vec.data[0][1];
        printf("%I64d\n",pw(x,pq,p));
        
    }
}