// Problem: CF1542B Plus and Multiply
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1542B
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>

// typedef int (long long) ;

using namespace std ;

typedef long long ll ;
unsigned long long n ;
unsigned long long T ;
unsigned long long a , b ;
long long q ;

signed main ( ) {
	cin >> T ;
	while(T--) {
		cin >> n >> a >> b ;
		bool flag = 0 ;
		if(b==1)flag = 1 ;
		q = 1;
		for ( int i = 0 ; i <= 30 ; i ++ ) {
			if(n%b==q%b) {
				// cout << "Yes" << endl ;
				flag = 1 ;
				break ;
			}
			q*=a ;
		}
		if(flag)cout << "Yes" << endl ;
		else cout << "No" << endl ;
	}
}