#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef string str;
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
typedef map<int,int> mii;
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound 
#define be begin
#define len length
const int MOD = 1e9+7;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

void init_code(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

ll power(ll n, int p){
    if(p == 0){
        return 1;
    }
    if(!(1&p)){
        return power(n*n,p/2);
    }else{
        return n * power(n*n,p/2);
    }
}


int main()
{   
    init_code();
    fastIO();
    //cout<<setprecision(12)<<fixed;
    int t=1;
    cin>>t;
    while(t--){
        ll n,a,b;
        cin>>n>>a>>b;
        if(b == 1){
            cout<<"Yes\n";
            continue;
        }
        if(a==1){
            if(n % b == 1){
                cout<<"Yes\n";
            }else{
                cout<<"No\n";
            }
            continue;
        }
        bool test = false;
        for(int i=0;true;i++){
            if(power(a,i) > n){
                break;
            }
            ll p = n - power(a,i);
            if(p % b == 0){
                test = true;
                break;
            }
        }
        if(test){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
}