import java.util.Scanner;
import java.math.BigInteger;

class Main {
    public static long mul(long a, long b, long mod){
        if (a == 1) return b;
        long tmp = mul(a/2, b, mod)%mod;
        if (a%2 == 1) return (tmp + tmp + b)%mod;
        return (tmp + tmp)%mod;

    }
    public static long power(long a, long b, long mod){
        if (b == 0) return 1;
        if (b == 1) return a;
        long tmp = power(a, b/2, mod)%mod;
        tmp = (tmp*tmp)%mod;
        if (b%2 == 1) return (tmp*a)%mod;
        return tmp;
    }

    public static void main (String[] args) throws java.lang.Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; ++i){
            long k = sc.nextLong();
            long a = sc.nextLong();
            long b = sc.nextLong();
            long base = sc.nextLong();
            long r = mul(a, power(base, k-1, b), b);            // a*base^(k-1)  %b
            BigInteger bR = new BigInteger(Long.toString(r));
            BigInteger bBase = new BigInteger(Long.toString(base));
            BigInteger bB = new BigInteger(Long.toString(b));
            System.out.println(bR.multiply(bBase).divide(bB));  // r*base   %b
        }
    }
}