#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<cassert>
#define copy COPY
#define LL long long
#define LD double
#define inf 10000000000000000ll
long long phi;
struct mat
{
    long long a[3][3];
    friend mat operator *(mat x,mat y)
    {
        mat ans;
        for (int i=0;i<=2;i++)
        for (int j=0;j<=2;j++)
        {
            ans.a[i][j]=0;
            for (int k=0;k<=2;k++) ans.a[i][j]+=x.a[i][k]*y.a[k][j];
            ans.a[i][j]%=phi;
        }
        return ans;
    }
};
mat make(LL p00,LL p01,LL p02,LL p10,LL p11,LL p12,LL p20,LL p21,LL p22)
{
    mat ans;
    ans.a[0][0]=p00;
    ans.a[0][1]=p01;
    ans.a[0][2]=p02;
    ans.a[1][0]=p10;
    ans.a[1][1]=p11;
    ans.a[1][2]=p12;
    ans.a[2][0]=p20;
    ans.a[2][1]=p21;
    ans.a[2][2]=p22;
    return ans;
}
mat getmi(mat a,long long b)
{
    if (b==1) return a;
    mat ans=getmi(a,b/2);
    ans=ans*ans;
    if (b%2) ans=ans*a;
    return ans;
}
long long getmi(long long a,long long b,long long mo)
{
    if (!b) return 1%mo;
    long long ans=getmi(a,b/2,mo);
    ans=ans*ans%mo;
    if (b%2) ans=ans*a%mo;
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    while (t--)
    {
        long long n,a,b,c,mo;
        scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&mo);
        if (n==1) {printf("%I64d\n",1%mo);continue;}
        if (n==2) {printf("%I64d\n",b%mo);continue;}
        phi=mo-1;
        mat m=make(0,1,0,1,c%phi,0,0,1,1);
        m=getmi(m,n-2);
        long long ans=0*m.a[0][1]+b*m.a[1][1]+b*m.a[2][1];
        printf("%I64d\n",getmi(a%mo,ans,mo));
    }
}