D. Мадока и лучшая школа России
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мадока собирается поступить в «ЦНУС ПТУ». Но на вступительном экзамене по информатике ей попалась сложная задача:

  • Число называется хорошим, если оно кратно $$$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» будут распознаны как положительный ответ).

Пример
Входные данные
8
6 2
12 2
36 2
8 2
1000 10
2376 6
128 4
16384 4
Выходные данные
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$$$ не являетcя хорошим.

В третьем примере $$$36$$$ можно представить в виде $$$18 \cdot 2$$$ и $$$6 \cdot 6$$$. Поэтому его можно разложить хотя бы двумя способами.