#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define answer(x) cout << (x ? "Yes\n" : "No\n")
#define test int t; cin >> t; while(t--)
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
using namespace std;

ll fstPw(ll x, ll y)
{
    if(y == 0)
        return 1;
    if(y & 1)
        return  x  * fstPw(x, y - 1);
    ll z = fstPw(x, y / 2);
    return z * z;
} 

// n = a ^ i + b * j 

int main()
{
    test
    { 
        ll n , a , b , ans = 0 , pw; 
        cin >> n >> a >> b; 
         
        for(int i=0 ; i <=30 ; i++)
        {
            pw = fstPw(a,i);

            if(pw > n) break; 

            if( (n-pw)%b == 0) ans = 1;
        }
        
        answer(ans);
    }
}