rt

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define pii pair<int,int>
using namespace std;
int T;
long long n,a,b;
int main()
{
	cin>>T;
	while(T--)
	{
		scanf("%lld%lld%lld",&n,&a,&b);
		long long s=n%b;
		if(a==1)
		{
			if(n%b==1 || n==1 || b==1)printf("Yes\n");
			else printf("No\n");
			continue;
		}
		bool flag=false;
		for(int i=1;i<=n;i*=a)
			if(i%b==s){flag=true;break;}
		if(flag)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}