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

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.