F. Василий любит теорию чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Василий - умный студент, и его преподаватель дискретной математики Соня хорошо преподала ему теорию чисел.

Он дал Огнену положительное целое число $$$n$$$.

Обозначим $$$d(n)$$$ как количество положительных делителей числа $$$n$$$, а $$$gcd(a, b)$$$ как наибольшее целое число $$$g$$$, такое что $$$a$$$ делится на $$$g$$$ и $$$b$$$ делится на $$$g$$$.

После этого он дал Огнену $$$q$$$ запросов, и есть $$$2$$$ типа запросов.

  • $$$1$$$, $$$x$$$ — сделать $$$n$$$ равным $$$n \cdot x$$$, а затем ответить на следующий вопрос: существует ли положительное целое число $$$a$$$, такое что $$$gcd(a, n) = 1$$$, и $$$d(n \cdot a) = n$$$?
  • $$$2$$$ — сбросить $$$n$$$ до его исходного значения (до применения запросов).

Обратите внимание, что $$$n$$$ не возвращается к своему исходному значению после запроса типа 1.

Поскольку Огнен боится теории чисел, Василий обещал ему, что после каждого запроса $$$d(n) \le 10^9$$$, однако, даже с таким ограничением, ему все равно нужна ваша помощь с этой задачей.

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

Первая строка содержит положительное целое число $$$t$$$, ($$$1 \le t \le 100$$$)  — количество наборов входных данных.

Первая строка каждого набора содержит $$$2$$$ целых числа, $$$n$$$ и $$$q$$$ ($$$1 \le n \le 10^{6}$$$, $$$1\le q \le 1000$$$) — число $$$n$$$ и количество запросов.

Следующие $$$q$$$ строк содержат целое число $$$k$$$ ($$$1 \le k \le 2$$$), если $$$k=1$$$, то в этой строке есть еще одно целое число $$$x$$$ ($$$1 \le x \le 10^6$$$)  — описание запросов.

Гарантируется, что для данного ввода $$$d(n)$$$ в любой момент не превышает $$$10^9$$$.

Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превышает $$$10^3$$$.

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

Для каждого запроса типа 1, вы должны вывести «YES», если существует такое положительное $$$a$$$, что $$$gcd(a, n) = 1$$$ и $$$d(n \cdot a)=n$$$, и «NO» в противном случае.

Вы можете вывести ответ в любом регистре (например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
7
1 5
1 1
1 2
2
1 8
1 9
20 4
1 3
2
1 7
1 12
16 10
1 6
1 6
1 10
1 9
1 1
1 9
1 7
1 3
1 2
1 10
9 1
1 3
8 1
1 2
8 3
1 5
1 8
1 10
11 5
1 8
1 2
1 1
1 3
1 1
Выходные данные
YES
YES
YES
YES

YES
NO
YES

YES
NO
YES
YES
YES
NO
YES
NO
YES
YES

NO

NO

YES
NO
NO

YES
NO
NO
NO
NO
Примечание

В первом наборе примера, изначально $$$n=1$$$.

После первого запроса: $$$n=1$$$, $$$d(n)=1$$$, поэтому, взяв $$$a = 1$$$, $$$d(n \cdot a) = n$$$, и ответ на этот запрос «YES».

После второго запроса: $$$n=2$$$, $$$d(n)=2$$$, мы можем снова взять $$$a = 1$$$, $$$d(n \cdot a) = n$$$, и ответ на этот запрос «YES».

После третьего запроса $$$n=1$$$, и это запрос типа $$$2$$$, поэтому мы не отвечаем на него.

После четвертого запроса: $$$n=8$$$, и взяв $$$a=3$$$, $$$d(n \cdot a) = d(24) = 8 = n$$$, поэтому ответ «YES».

После пятого запроса: $$$n=72$$$, теперь мы можем взять $$$a=637$$$, чтобы получить $$$n \cdot a = 45864$$$, и $$$d(n \cdot a) = 72 = n$$$, поэтому ответ «YES».

Во втором наборе примера, изначально $$$n=20$$$.

После первого запроса: $$$n=60$$$, и ответ «YES».

После второго запроса: $$$n=20$$$, это запрос типа $$$2$$$, поэтому мы не отвечаем на него.

После третьего запроса: $$$n=140$$$, и можно доказать, что независимо от того, какое положительное целое число $$$a$$$ мы возьмем, $$$d(n \cdot a)$$$ никогда не будет равно $$$n$$$, поэтому ответ на этот запрос «NO».

После четвертого запроса: $$$n=1680$$$. Можно доказать, что существует положительное целое число $$$a$$$, такое что $$$d(n \cdot a) = n$$$, поэтому ответ «YES».