Plus and Multiply

题面翻译

有一个无穷大的正整数集合 $S$，该集合按下面所述方法生成：

• 数字 $1$ 在集合 $S$ 中。
• 若数字 $x$ 在该集合中，那么数 $x \times a$ 和数 $x+b$ 均在集合 $S$ 中。（其中 $a$ 与 $b$ 为给定常数）

现在给出数 $n,a,b$，请判断 $n$ 是否在集合 $S$ 中（此处给出的 $a$ 与 $b$ 就是上述集合生成方法中的 $a$ 和 $b$），若在请输出 Yes，否则输出 No。多组数据。

令数据组数为 $t$，那么有 $1 \leq t \leq 10^5$，$1 \leq n,a,b \leq 10^9$。

题目描述

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.

样例 #1

样例输入 #1

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

样例输出 #1

Yes
No
Yes
No
Yes

提示

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.