You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

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

## Examples
```input
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
```
```output
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
```

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

Now solve the problem and return the code.