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.

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$ .

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).

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".