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

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

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

Vasilije Loves Number Theory

Examples