#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

long long a,b,c,n,p,t,P;
int T;

struct matrix{
    long long a[3][3];
}ans,temp;

matrix operator*(matrix a,matrix b){
    matrix c;
    int i,j,k;
    memset(c.a,0,sizeof(c.a));
    for (k=0;k<3;k++){
        for (i=0;i<3;i++){
            for (j=0;j<3;j++){
                c.a[i][j]+=a.a[i][k]*b.a[k][j];
                c.a[i][j]%=p;
            }
        }
    }
    return c;
}


long long power(long long a,long long b){
    long long temp=1;
    while (b){
        if (b&1) temp=(temp*a)%P;
        b>>=1;
        a=a*a %P;
    }
    return temp;
}

matrix power(matrix a,long long b){
    matrix temp;
    temp.a[0][0]=1;temp.a[0][1]=0;temp.a[0][2]=0;
    temp.a[1][0]=0;temp.a[1][1]=1;temp.a[1][2]=0;
    temp.a[2][0]=0;temp.a[2][1]=0;temp.a[2][2]=1;
    
    while (b){
        if (b&1) temp=temp*a;
        a=a*a;
        b>>=1;
    }
    return temp;
}


int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&P);
        p=P-1;
        if (n==1){
            printf("1\n");
            continue;
        }
        t=power(a,b);
        ans.a[0][0]=1;
        ans.a[0][1]=0;
        ans.a[0][2]=1;
        
        temp.a[0][0]=c;temp.a[0][1]=1;temp.a[0][2]=0;
        temp.a[1][0]=1;temp.a[1][1]=0;temp.a[1][2]=0;
        temp.a[2][0]=1;temp.a[2][1]=0;temp.a[2][2]=1;
        
        ans=ans*power(temp,n-2);
        printf("%lld\n",power(t,ans.a[0][0]));
    }
    return 0;
}