#include<bits/stdc++.h>
using namespace std;
int main(){
	std::ios::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	queue<long long> qwq;
	int T;
	cin>>T;
	for(int i=0;i<T;i++){
		long long a,b,c,p;
		int cishu=0;
		bool flag=1;
		cin>>p>>a>>b>>c;
		qwq.push(0%p);
		qwq.push(b%p);
		while(!qwq.empty()&&cishu<=400000&&flag){
		    if(qwq.front()==c||qwq.back()==c){
		        cout<<"Yes\n";
		        flag=0;
		        continue;
		    }
			if(qwq.front()*a%p==c){
				cout<<"Yes\n";
				flag=0;
				continue;
			}
			
			if((qwq.front()+b)%p==c){
				cout<<"Yes\n";
				flag=0;
				continue;
			}
			qwq.push((qwq.front()+b)%p);
			qwq.push((qwq.front()*a)%p);
			qwq.pop();
			cishu++; 
		}
		if(flag||cishu>=400000)
			cout<<"No\n";
		while(!qwq.empty())
			qwq.pop();
	}
	return 0; 
}