A14463 | Plus and Multiply

There is an infinite set generated as follows:

- $1$ is in this set.
- If $x$ is in this set, $x \cdot 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\cdot 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\cdot 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.

The input consists of multiple test cases. The first line contains an integer $t$ ( $1\leq t\leq 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\leq n,a,b\leq 10^9$ ) separated by a single space.

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