有一个无限集生成如下:
- $$$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$$$是否在这个集合中。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
描述每个测试用例的唯一行包含三个整数 $$$n$$$、$$$a$$$、$$$b$$$ ($$$1\leq n,a,b\leq 10^9$$$),并用一个空格分隔。
输出
对于每个测试用例,如果 $$$n$$$ 在此集合中,则打印“Yes”,否则打印“No”。您可以在任何情况下打印每个字母。
示例
输入 #1
5 24 3 5 10 3 6 2345 1 4 19260817 394 485 19260817 233 264
输出 #1
Yes No Yes No Yes
注意
在第一个测试用例中,$$$24$$$ 生成如下:
- $$$1$$$ 在这个集合中,所以 $$$3$$$ 和 $$$6$$$ 在这个集合中;
- $$$3$$$ 在这个集合中,所以 $$$9$$$ 和 $$$8$$$ 在这个集合中;
- $$$8$$$ 在这个集合中,所以 $$$24$$$ 和 $$$13$$$ 在这个集合中。
因此我们可以看到 $$$24$$$ 在这个集合中。
第二个测试用例中集合的五个最小元素在语句中进行了描述。我们可以看到 $$$10$$$ 不在其中。