#include<bits/stdc++.h>
using namespace std;
#define ps(x,y)         fixed<<setprecision(y)<<x
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define int               long long
typedef long long ll;
ll mod = 1000000007;
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll mul(ll x, ll y)
{
    return (x * 1ll * y) % mod;
}
ll binpow(ll x, ll y)
{   
    ll z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
ll add(ll x, ll y)
{
    return((x%mod)+(y%mod))%mod;
}
// KMP
// longest prefix which is also suffix
// compute lps array is used for pre computing the pattern
void computeLPSArray(char* pat, int M, int* lps)
{
    // length of the previous longest prefix suffix
    int len = 0;
  
    lps[0] = 0; // lps[0] is always 0
  
    // the loop calculates lps[i] for i = 1 to M-1
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];
  
                // Also, note that we do not increment
                // i here
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
int KMP(char* pat, char* txt)
{
    int M = strlen(pat);
    int N = strlen(txt);
  
    // create lps[] that will hold the longest prefix suffix
    // values for pattern
    int lps[M];
  
    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);
  
    int i = 0; // index for txt[]
    int j = 0; // index for pat[]
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
  
        if (j == M) {
           return i-j;
            j = lps[j - 1];
        }
  
        // mismatch after j matches
        else if (i < N && pat[j] != txt[i]) {
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return -1;
}
// return the length of longest prefix which is palindromic
int longestpalindromprefix(string s)
{
    vector<int> lpp(s.size(),0);
    for(int i=1;i<s.size();i++)
    {
        int prev = lpp[i-1];
        while(prev>0 and s[i]!=s[prev])
        {
            prev = lpp[prev-1];
        }
        lpp[i] = prev + (s[i]==s[prev]?1:0);
    }
    return lpp[s.size()-1];
}
int largestpalpre(string s)
{
    string t = s + "?";
    reverse(s.begin(),s.end());
    t+=s;
    return longestpalindromprefix(t);
}
bool ispalindrome(string s)
{
    int n = s.length();
    bool flg=true;
    int i=0,j=n-1;
    while(i<j)
    {
        if(s[i]==s[j])
        {
            i++;
            j--;
        }else{
            flg=false;
            break;
        }
    }
    return flg;
}
void solve()
{
    int n,a,b;
    cin>>n>>a>>b;
    if(b==1)
    {
        cout<<"Yes\n";
        return;
    }else if(a==1)
    {
        int x = n-1;
        if(x%b==0)
        {
            cout<<"Yes\n";
            return;
        }else
        {
            cout<<"No\n";
            return;
        }
    }else
    {
        vector<int>pows;
        int curp=1;
        pows.push_back(curp);
        while(true)
        {
            if(curp*a<=1e9)
            {
                curp*=a;
                pows.push_back(curp);
            }else
            {
                break;
            }
        }
        bool flag=false;
        int nn = pows.size();
        rep(i,0,nn)
        {
            int tmp = n - pows[i];
            if(tmp>=0 and tmp%b==0)
            {
                flag=true;
                break;
            }
        }
        if(flag)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output2.txt","w",stdout);
#endif
    FIO;
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}