Q=int(input())
for _ in range(Q):
  N,M,L,mod=map(int,input().split())
  h=[[[0]*4 for j in range(4)] for k in range(60)]
  h[0][0]=[0,M,L,0]
  h[0][1]=[1,0,0,L]
  h[0][2]=[1,0,0,M]
  h[0][3]=[0,1,1,0]
  for k in range(1,60):
    for i in range(4):
      for j in range(4):
        for w in range(4):
          h[k][i][j]+=h[k-1][i][w]*h[k-1][w][j]
          h[k][i][j]%=mod
  A=[[0]*4 for i in range(4)]
  for i in range(4):
    A[i][i]=1
  for k in range(60):
    if (N>>k)&1:
      A2=[[0]*4 for i in range(4)]
      for i in range(4):
        for j in range(4):
          for w in range(4):
            A2[i][j]+=A[i][w]*h[k][w][j]
            A2[i][j]%=mod
      for i in range(4):
        for j in range(4):
          A[i][j]=A2[i][j]
  if N%2==0:
    result=A[0][0]
  else:
    result=A[2][0]
  print(result)