Василий - умный студент, и его преподаватель дискретной математики Соня хорошо преподала ему теорию чисел.
Он дал Огнену положительное целое число \(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\), однако, даже с таким ограничением, ему все равно нужна ваша помощь с этой задачей.
Выходные данные
Для каждого запроса типа 1, вы должны вывести «YES», если существует такое положительное \(a\), что \(gcd(a, n) = 1\) и \(d(n \cdot a)=n\), и «NO» в противном случае.
Вы можете вывести ответ в любом регистре (например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ).
Примечание
В первом наборе примера, изначально \(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».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|