```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
int T;
bool flag;
int a,n,b,p;
map<int,int> phi;
int get_phi(int x){
	if(phi[x])return phi[x];
	int ans=x;
	for(int i=2;i*i<=x;i++)if(x%i==0){
		ans=ans/i*(i-1);
		while(x%i==0)x/=i;
	}
	if(x!=1)ans=ans/x*(x-1);
	return phi[x]=ans;
}
int mod(ll a,int p){
	return a<p?a:a%p+p;
}
int power(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1)ans=mod(1ll*ans*a,p);
		a=mod(1ll*a*a,p);
		b>>=1;
	}
	return ans;
}
int dfs(int a,int n,int p){
	if(p==1)return flag=false,0;
	if(n==1)return mod(a,p);
	return power(a,dfs(a,n-1,get_phi(p)),p);
}
int BSGS(int x,int y,int p){
	map<int,int> mp;
	int t=sqrt(p)+1,cur=1;
	for(int i=1;i<=t;i++){
		cur=1ll*cur*x%p;
		mp[1ll*cur*y%p]=i;
	}
	int now=cur;
	for(int i=1;i<=t;i++){
		if(mp[now])return i*t-mp[now];
		now=1ll*now*cur%p;
	}
	return -1;
}
signed main(){
	scanf("%lld",&T);
	for(int line=1;line<=T;line++){
		scanf("%lld%lld%lld%lld",&a,&n,&b,&p);
		if(b==1||p==1){
			puts("0");
			continue;
		}
		if(n==1)printf("%lld\n",BSGS(a,b,p));
		else if(n==2){
			flag=true;
			int ans=-1;
			for(int i=1;flag;i++)if(dfs(a,i,p)%p==b){
				ans=i;
				break;
			}
			printf("%lld\n",ans);
		}
		else{
            if(a==1)puts("-1");
            else if(b==a%p)puts("1");
            else if(a==2){
                if(b==dfs(a,2,p)%p)puts("2");
                else if(b==dfs(a,16,p)%p)puts("3");
                else if(b==dfs(a,100,p)%p)puts("4");
                else puts("-1");
            }
            else if(b==dfs(a,a,p)%p)puts("2");
            else if(b==dfs(a,100,p)%p)puts("3");
            else puts("-1");
        }
	}
}/*
1
7 3 1 4
*/