1542B.cpp

#include <bits/stdc++.h>
using namespace std;
//
#define ll long long
#define ull unsigned long long
#define mx 100010
#define mod 1000000007
#define inf INT_MAX
#define pi acos(-1)
#define endl '\n'
#define pb push_back
#define pll pair<ll, ll>
#define Fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//
int main() {
    ll t;
    cin >> t;

    while (t--) {
        ull n, a, b;
        cin >> n >> a >> b;

        if (a == 1 && b != 1) {
            if (n % b == 1) cout << "Yes" << endl;
            else cout << "No" << endl;
            continue;
        }
        else if (b == 1) {
            cout << "Yes" << endl;
            continue;
        }

        ull j = 0;
        while (1) {
            ull x = pow(a, j++);
            if (x > n) {
                cout << "No" << endl;
                break;
            }
            if ((n - x) % b == 0) {
                cout << "Yes" << endl;
                break;
            }
        }
    }
}