CF1878F.Vasilije Loves Number Theory

Vasilije is a smart student and his discrete mathematics teacher Sonja taught him number theory very well.

He gave Ognjen a positive integer $n$.

Denote $d(n)$ as the number of positive integer divisors of $n$, and denote $gcd(a, b)$ as the largest integer $g$ such that $a$ is divisible by $g$ and $b$ is divisible by $g$.

After that, he gave Ognjen $q$ queries, and there are $2$ types of queries.

• $1$, $x$ — set $n$ to $n \cdot x$, and then answer the following question: does there exist a positive integer $a$ such that $gcd(a, n) = 1$, and $d(n \cdot a) = n$?
• $2$ — reset $n$ to its initial value (before any queries).

Note that $n$ does not get back to its initial value after the type 1 query.

Since Ognjen is afraid of number theory, Vasilije promised him that after each query, $d(n) \le 10^9$, however, even with that constraint, he still needs your help with this problem.

瓦西利耶是一位聪明的学生，他的离散数学老师索尼亚将数论知识教得非常好。

他给了奥格年一个正整数 $n$。

记 $d(n)$ 为 $n$ 的正整数约数的个数，记 $gcd(a, b)$ 为最大的整数 $g$，使得 $a$ 和 $b$ 均能被 $g$ 整除。

接着，他给了奥格年 $q$ 个查询，查询分为两类：

• $1\ x$ —— 将 $n$ 更新为 $n \cdot x$，然后回答如下问题：是否存在一个正整数 $a$，满足 $gcd(a, n) = 1$，且 $d(n \cdot a) = n$？
• $2$ —— 将 $n$ 重置为其初始值（即所有查询执行前的原始值）。

注意：在类型 1 的查询中，$n$ 不会自动恢复为初始值。

由于奥格年害怕数论，瓦西利耶向他保证：每次查询之后均有 $d(n) \le 10^9$。然而，即便有这一约束，他仍需要你的帮助来解决此问题。

The first line contains a positive integer $t$, ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains $2$ integers, $n$ and $q$ ($1 \le n \le 10^{6}$, $1\le q \le 1000$) — the number $n$ and the number of queries.

The following $q$ lines contain an integer $k$ ($1 \le k \le 2$), if $k=1$ then there is another integer in this line $x$ ($1 \le x \le 10^6$) — the description of the queries.

It is guaranteed that, for the given input, $d(n)$ does not exceed $10^9$ at any point.

It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^3$.

第一行包含一个正整数 $t$（$1 \le t \le 100$）——测试用例的数量。

每个测试用例的第一行包含两个整数 $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$。

For each type 1 query, you should output "YES" if there exist such positive integer $a$ that $gcd(a, n) = 1$ and $d(n \cdot a)=n$, and "NO" if he can't.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

对于每个类型 1 的查询，若存在正整数 $a$ 满足 $\gcd(a, n) = 1$ 且 $d(n \cdot a)=n$，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写形式输出答案（例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均被视为肯定回答）。

In the first test case, we initially have $n=1$.

After the first query: $n=1$, $d(n)=1$, so by taking $a = 1$, $d(n \cdot a) = n$, and the answer to this query is "YES".

After the second query: $n=2$, $d(n)=2$, we can, again, take $a = 1$, $d(n \cdot a) = n$, and the answer to this query is "YES".

After the third query $n=1$, and this is a type $2$ query so we don't answer it.

After the fourth query: $n=8$, and by taking $a=3$, $d(n \cdot a) = d(24) = 8 = n$, so the answer is "YES".

After the fifth query: $n=72$, now we can take $a=637$ to get $n \cdot a = 45864$, and $d(n \cdot a) = 72 = n$, so the answer is "YES".

In the second test case, we initially have $n=20$.

After the first query: $n=60$, and the answer is "YES".

After the second query: $n=20$, this is a type $2$ query, so we don't answer it.

After the third query: $n=140$, and it can be proven that no matter which positive integer $a$ we take, $d(n \cdot a)$ will never be equal to $n$, so the answer to this query is "NO".

After the fourth query: $n=1680$. It can be proven that there exists a positive integer $a$, such that $d(n \cdot a) = n$, so the answer is "YES".

在第一个测试用例中，初始时 $n=1$。

第一次查询后：$n=1$，$d(n)=1$，此时取 $a = 1$，有 $d(n \cdot a) = d(1) = 1 = n$，因此该查询的答案为 “YES”。

第二次查询后：$n=2$，$d(n)=2$，同样可取 $a = 1$，满足 $d(n \cdot a) = d(2) = 2 = n$，因此该查询的答案为 “YES”。

第三次查询：$n=1$，这是一个类型 $2$ 的查询，因此无需回答。

第四次查询：$n=8$，此时取 $a=3$，有 $n \cdot a = 24$，且 $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”。