#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define rpt(i,l,r) for(int i=l;i<=r;i++)
#define rpd(i,r,l) for(int i=r;i>=l;i--)
struct matrix{
    int v[3][3];
}d,e,I;
int m;
matrix operator *(matrix a,matrix b){
    matrix res;
    memset(res.v,0,sizeof(res.v));
    rpt(i,0,2) rpt(j,0,2) rpt(k,0,2)
        (res.v[i][j]+= (int)((long long)a.v[i][k]*b.v[k][j]%(m-1)) )%=(m-1);
    return res;
}
matrix operator ^(matrix a,long long x){
    matrix res=I;
    while(x){
        if(x&1) res=res*a;
        x>>=1;a=a*a;
    }
    return res;
}
long long mi(long long x,long long y){
    if(y==0) return 1;
    long long temp=mi(x,y>>1);
    (temp*=temp)%=m;
    if(y&1) (temp*=x)%=m;
    return temp;
}
int T;
long long n;
int a,b,c;
int main(){I=(matrix){1,0,0,0,1,0,0,0,1};
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%d%d%d%d",&n,&a,&b,&c,&m);
        if(n==1) printf("1\n");
        else{
            d=(matrix){1,0,0,0,0,0,1,0,0};
            e=(matrix){c,1,1,1,0,0,0,0,1};
            d=(e^(n-2))*d;
            printf("%I64d\n",mi(mi(a,b),d.v[0][0]));
        }
        
    }
}