Lynk 最近正在研究 Collatz 猜想。Collatz 猜想是一个数学猜想，其内容如下：

• 从任意正整数 $n$ 开始，执行以下步骤：
  • 如果 $n$ 是偶数，将其除以 2：$n \to \frac{n}{2}$。
  • 如果 $n$ 是奇数，将其乘以 3 再加 1：$n \to 3n + 1$。
• 无限重复此过程。该猜想声称，无论 $n$ 的初始值是多少，序列最终都会达到 1。

Lynk 很快解决了 Collatz 猜想，并决定研究它的一个变体。在这个问题中，有两个互质的参数 $A$ 和 $B$。

• 从任意正整数 $n$ 开始，执行以下步骤：
  • 如果 $n$ 是 $A$ 的倍数，将其除以 $A$：$n \to \frac{n}{A}$；
  • 否则，加上 $B$：$n \to n + B$。

他发现，在这个问题中，并非所有的数字最终都会变成 1。在他的实验中，有些数字在最初的几步中增长很快，而有些则最终进入了一个循环。根据他的观察，他推测某些满足特定条件的整数最终会回到自身。对于给定的正整数 $n$，他试图确定它是否会在有限步数后回到自身。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $A, B, n$ ($2 \le A \le 10^9, 1 \le B \le 10^9, 1 \le n \le 10^{18}$)。保证 $A$ 和 $B$ 互质。

输出格式

对于每个测试用例：

• 如果 $n$ 会在有限步数后回到自身，输出 Yes。
• 否则，输出 No。

样例

样例输入 1

7
2 1 1
2 1 2
2 1 3
2 1 100
314 159 265
314 159 2653
314 159 26535

样例输出 1

Yes
Yes
No
No
Yes
Yes
No