#include <stdio.h>

 int gcd(int a, int b)

 {

     return !b ? a : gcd(b, a%b);

 }

 int mod_pow(int a, int x, int mod)

 {

     int tmp = a;

     int ret = ;

     while(x) {

         if (x & ) {

             ret = ret * tmp % mod;

         }

         tmp = tmp * tmp % mod;

         x >>= ;

     }

     return ret;

 }

 int main()

 {

     int t, a, m, n, k;

     scanf("%d", &t);

     while (t--) {

         scanf("%d %d %d %d", &a, &m, &n, &k);

         int d = gcd(m, n);

         int ans = mod_pow(a, d, k);

         printf("%d\n", (ans -  + k) % k);

     }

     return ;

 }