#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, bool> pib;
const int maxn = 40;
int t, tot, a, n, b, p, f[maxn];
pib qpow(int a, int b, int p) {
    int res = 1; bool B = false;
    for (; b; b >>= 1, B |= (ll)a * a >= p, a = (ll)a * a % p)
        if (b & 1) B |= (ll)res * a >= p, res = (ll)res * a % p;
    return {res, B};
}
int bsgs(int a, int n, int p) {
    map<int, int> h;
	int B = 0; while (B * B < p) ++B;
	for (int i = 0; i <= B; i++)
		h[n] = i, n = (ll)n * a % p;
	int A = qpow(a, B, p).first, cur = 1;
	for (int i = 1; i <= B; i++) {
		cur = (ll)cur * A % p;
		if (h[cur]) return i * B - h[cur];
	} return -1;
}
int phi(int n) {
    int res = n; 
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) res = res / n * (n - 1);
    return res;
}
pib solve(int a, int n, int p){ 
	if (f[p] == 1) return {0, 1};
	if (!n) return {1, 0};
    auto [v, k] = solve(a, n - 1, p + 1);
	return qpow(a, v + (k ? f[p + 1] : 0), f[p]);
}
int calc(int a, int n) {
    if (!n) return 1;
    return solve(a, calc(a, n - 1), 0).first;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> a >> n >> b >> p;
        if (n == 1) cout << bsgs(a, b, p) << '\n';
        else {
			tot = 0; for (int i = p; i != 1; i = phi(i)) f[tot++] = i;
			f[tot] = 1; int ans = -1;
			for (int i = 0; i <= (n == 2 ? tot : 13); i++)
				if ((n == 2 && solve(a, i, 0).first == b) || (n == 3 && calc(a, i) == b)) {
					ans = i;
					break;
				}
			cout << ans << '\n';
        }
    }
    return 0;
}