#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>
  
using namespace std;
  
#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
  
typedef  long long LL;
  
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<‘0‘||CH>‘9‘;F= CH==‘-‘,CH=getchar());
    for(num=0;CH>=‘0‘&&CH<=‘9‘;num=num*10+CH-‘0‘,CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + ‘0‘);
    putchar(‘\n‘);
}
  
//const LL mod=1e9+7;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=(1<<20)+10;
const int maxn=1e5+10;
const double eps=1e-12;
 
LL prime[maxn],mod;
int vis[maxn],cnt=0;
struct matrix 
{
    LL a[2][2];
};
matrix cal(matrix A,matrix B)
{
    matrix C;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<=2;j++)
        {
            C.a[i][j]=0;
            for(int k=0;k<2;k++)
            {
                C.a[i][j]+=A.a[i][k]*B.a[k][j];
                C.a[i][j]%=mod;
            }
        }
    }
    return C;
}

LL pow_mod(LL y)
{
    if(y==0)return 0;
    else if(y==1)return 1;
    else if(y==2)return 2;
    else y-=2;
    matrix s,base;
    s.a[0][0]=s.a[1][1]=1;s.a[0][1]=s.a[1][0]=0;
    base.a[0][0]=2,base.a[0][1]=base.a[1][0]=1,base.a[1][1]=0;
    while(y)
    {
        if(y&1)s=cal(s,base);
        base=cal(base,base);
        y>>=1;
    }
    return (s.a[0][0]*2+s.a[0][1])%mod;
}
inline void Init()
{
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            for(int j=2*i;j<maxn;j+=i)vis[j]=1;
            prime[++cnt]=(LL)i;
        }
    }
}
LL phi(LL fx)
{
    LL s=fx;
    for(int i=1;i<=cnt;i++)
    {
        if(fx<prime[i])break;
        if(fx%prime[i]==0)
        {
            s=s/prime[i]*(prime[i]-1);
            while(fx%prime[i]==0)fx/=prime[i];
        }
    }
    if(fx>1)s=s/fx*(fx-1);
    return s;
}
LL powmod(LL a,LL b,LL mo)
{
  LL s=1,base=a;
  while(b)
  {
    if(b&1)s=s*base%mo;
    base=base*base%mo;
    b>>=1;
  }
  return s;
}
int main()
{
    Init();
    int t;
    LL n,y,x,s;
    read(t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld",&n,&y,&x,&s);
        s++;
        mod=phi(s)*2;
        LL ans=pow_mod(n*y)*pow_mod(n*y+1)%mod/2+mod/2;
        ans=powmod(x,ans,s);
        printf("%lld\n",ans);
    }
    return 0;
}