题目描述

天天抓住那头牛，牛开始反击了。

已知牛在数轴上，初始的位置是 $1$，每次牛可以往正方向走 $a$ 单位长度，或走到当前位置的 $b$ 倍的位置。即如果牛的位置为 $x$，牛可以走到 $x+a$ 或 $x\times b$。求 33DAI 所在的位置 $pos$ 会不会被牛抓住（牛能不能走到 $pos$）。

输入格式

第一行为整数 $T$，有 $T$ 次询问。

接下来 $T$ 行，每行包括三个整数 $a,b,pos$，即当前询问。

输出格式

输出 $T$ 行，对应 $T$ 次询问。如果第 $i$ 次询问中 33DAI 会被抓到，就输出 YES，否则输出 NO。

5
1 5 33
3 2 17
7 2 32
6 3 10
6 3 9

YES
YES
YES
NO
YES

样例解释

• $1\times 5\times 5+1+1+1+1+1+1+1+1 = 33$
• $(1+3+3)\times 2 + 3 = 17$
• $(1+7)\times 2\times 2 = 32$
• 抓不到 33DAI
• $1\times 3 + 6 = 9$

数据规模与约定

对于 $100\%$ 的数据，$1 \le T\le 10^4$，$1\le a,b,pos\le 10^9$

• 子任务 1（30 分）：保证 $b=1$。
• 子任务 2（30 分）：保证 $T=1$，$1\le a,b,pos\le 10^7$。
• 子任务 3（40 分）：没有特殊限制。