小圆即将报名参加“TSUNS PTU”。但她在计算机科学入学考试期间偶然发现了一个艰巨的任务:
- 如果一个数字是 $$$d$$$ 的倍数,则该数字被称为好数字。
- 如果一个数字是好的并且不能表示为两个好数字的乘积,则该数字被称为美丽的。
注意,漂亮的数字一定是好的。
给定一个好数字 $$$x$$$,确定它是否可以用至少两种不同的方式表示为几个(可能是一个)漂亮数字的乘积。如果使用的数字组不同,则两种方法是不同的。
为小圆解决这个问题,帮助她进入俄罗斯最好的学校!
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。以下是他们的描述。
每个测试用例由两个整数 $$$x$$$ 和 $$$d$$$ 组成,用空格分隔 ($$$2 \leq x, d \leq 10^9$$$)。保证 $$$x$$$ 是 $$$d$$$ 的倍数。
输出
对于每组输入数据,如果数字不能以至少两种方式表示,则输出“NO”。否则,输出“YES”。
您可以在任何情况下输出每个字母(例如,“YES”、“Yes”、“yes”、“yEs”、“yEs”将被识别为肯定答案)。
示例
输入 #1
8 6 2 12 2 36 2 8 2 1000 10 2376 6 128 4 16384 4
输出 #1
NO NO YES NO YES YES NO YES
注意
在第一个示例中,$$$6$$$ 可以表示为 $$$6$$$、$$$1 \cdot 6$$$、$$$2 \cdot 3$$$。但是 $$$3$$$ 和 $$$1$$$ 不是一个好数字,因为它们不能被 $$$2$$$ 整除,所以只有一种方法。
在第二个示例中,$$$12$$$ 可以表示为 $$$6 \cdot 2$$$、$$$12$$$、$$$3 \cdot 4$$$ 或 $$$3 \cdot 2 \cdot 2$$$。第一个选项是合适的。第二个是——不,因为 $$$12$$$ 不是一个漂亮的数字($$$12 = 6 \cdot 2$$$)。第三个和第四个也不合适,因为 $$$3$$$ 不是好数字。
在第三个示例中,$$$36$$$ 可以表示为 $$$18 \cdot 2$$$ 和 $$$6 \cdot 6$$$。因此它至少可以通过两种方式分解。