#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define FAST_IO ios_base::sync_with_stdio(false)
#define debug(x)           \
    cout << #x << ": [ ";  \
    for (auto &aa : x)     \
        cout << aa << " "; \
    cout << "]\n"
#define debug1(x) cout << "## " << #x << " : " << x << " ##\n"
#define debug2(x, y) cout << "## " << #x << " : " << x << " | " << #y << " : " << y << " ##\n"

const int MOD = 1e9 + 7;

ll binPow(ll n, ll p)
{
    if (p == 0)
        return 1;

    ll term = binPow(n, p / 2);
    term *= term;

    if (p % 2 == 1)
    {
        term *= n;
    }

    return term;
}

void solve()
{
    ll n, a, b;
    cin >> n >> a >> b;

    if (a == 1)
    {
        ll term = n - 1;
        if (term % b == 0)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
        return;
    }

    bool found = false;

    ll i = 0;
    while (true)
    {
        ll term = binPow(a, i);

        if (term > n)
            break;

        ll rem = n - term;

        if (rem % b == 0)
        {
            found = true;
            break;
        }
        i++;
    }

    if (found)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}

int main()
{

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

    FAST_IO;

    int test;
    cin >> test;
    //test=1;

    while (test--)
    {
        solve();
    }

    return 0;
}