#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
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) {
flag = 1 ;
break ;
}
q*=a ;
}
if(flag)cout << "Yes" << endl ;
else cout << "No" << endl ;
}
}