B. Сложить и умножить
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано бесконечное множество, сгенерированное следующим образом:

  • $$$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$$$), разделенных пробелом.

Выходные данные

Для каждого набора входных данных выведите «Yes», если $$$n$$$ принадлежит множеству, и «No» иначе. Вы можете выводить каждую букву в любом регистре (строчную или заглавную).

Пример
Входные данные
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
Выходные данные
Yes
No
Yes
No
Yes
Примечание

В первом наборе $$$24$$$ генерируется следующим образом:

  • $$$1$$$ лежит в множестве, поэтому $$$3$$$ и $$$6$$$ лежат в множестве;
  • $$$3$$$ лежит в множестве, поэтому $$$9$$$ и $$$8$$$ лежат в множестве;
  • $$$8$$$ лежит в множестве, поэтому $$$24$$$ и $$$13$$$ лежат в множестве.

Таким образом, $$$24$$$ принадлежит множеству.

Первые пять элементов множества из второго набора входных данных описаны в условии. Можно заметить, что $$$10$$$ не в их числе.