Problem: There is an infinite set generated as follows:

  * 1 is in this set. 
  * If x is in this set, x ⋅ a and x+b both are in this set. 



For example, when a=3 and b=6, the five smallest elements of the set are:

  * 1, 
  * 3 (1 is in this set, so 1⋅ a=3 is in this set), 
  * 7 (1 is in this set, so 1+b=7 is in this set), 
  * 9 (3 is in this set, so 3⋅ a=9 is in this set), 
  * 13 (7 is in this set, so 7+b=13 is in this set). 



Given positive integers a, b, n, determine if n is in this set.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 10^5) — the number of test cases. The description of the test cases follows.

The only line describing each test case contains three integers n, a, b (1≤ n,a,b≤ 10^9) separated by a single space.

Output

For each test case, print "Yes" if n is in this set, and "No" otherwise. You can print each letter in any case.

Example

Input


5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264


Output


Yes
No
Yes
No
Yes

Note

In the first test case, 24 is generated as follows:

  * 1 is in this set, so 3 and 6 are in this set; 
  * 3 is in this set, so 9 and 8 are in this set; 
  * 8 is in this set, so 24 and 13 are in this set. 



Thus we can see 24 is in this set.

The five smallest elements of the set in the second test case is described in statements. We can see that 10 isn't among them.

Solution (in CPP):

Solution:
#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();
    }
}