Description:
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.
Input Format:
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$$$.
Output Format:
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).
Note:
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".