CF1542B.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.

存在一个按如下方式生成的无限集合：

• $1$ 属于该集合；
• 若 $x$ 属于该集合，则 $x \cdot a$ 和 $x+b$ 均属于该集合。

例如，当 $a=3$ 且 $b=6$ 时，该集合中最小的五个元素为：

• $1$，
• $3$（因为 $1$ 属于该集合，所以 $1\cdot a=3$ 属于该集合），
• $7$（因为 $1$ 属于该集合，所以 $1+b=7$ 属于该集合），
• $9$（因为 $3$ 属于该集合，所以 $3\cdot a=9$ 属于该集合），
• $13$（因为 $7$ 属于该集合，所以 $7+b=13$ 属于该集合）。

给定正整数 $a$、$b$、$n$，判断 $n$ 是否属于该集合。

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.

输入包含多个测试用例。第一行包含一个整数 $t$（$1\leq t\leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含三个由单个空格分隔的整数 $n$、$a$、$b$（$1\leq n,a,b\leq 10^9$）。

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

对于每个测试用例，如果 $n$ 属于该集合，则输出 "Yes"；否则输出 "No"。每个字母的大小写不限。

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.

在第一个测试用例中，$24$ 的生成过程如下：

• $1$ 属于该集合，因此 $3$ 和 $6$ 也属于该集合；
• $3$ 属于该集合，因此 $9$ 和 $8$ 也属于该集合；
• $8$ 属于该集合，因此 $24$ 和 $13$ 也属于该集合。

由此可知，$24$ 属于该集合。

第二个测试用例中，该集合的五个最小元素已在题目描述中给出。我们可以看出，$10$ 并不在这五个数之中。