Codeforces Round 900 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

math

number theory

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Vasilije Loves Number Theory

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Example

Input

71 51 11 221 81 920 41 321 71 1216 101 61 61 101 91 11 91 71 31 21 109 11 38 11 28 31 51 81 1011 51 81 21 11 31 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".

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 08:58:41 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|