310740: CF1878F. Vasilije Loves Number Theory

F. Vasilije Loves Number Theorytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

ExampleInput

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

**题目大意：**

Vasilije 是一位聪明的学生，他的离散数学老师 Sonja 非常擅长教授数论。他给了 Ognjen 一个正整数 $ n $。

定义 $ d(n) $ 为 $ n $ 的正整数因子的数量，定义 $ gcd(a, b) $ 为最大的整数 $ g $，使得 $ a $ 能被 $ g $ 整除且 $ b $ 也能被 $ g $ 整除。

之后，他给了 Ognjen $ q $ 个查询，查询类型有 2 种：
1. $ 1 $, $ x $ —— 将 $ n $ 设置为 $ n \cdot x $，然后回答以下问题：是否存在一个正整数 $ a $ 使得 $ gcd(a, n) = 1 $ 且 $ d(n \cdot a) = n $？
2. $ 2 $ —— 将 $ n $ 重置为其初始值（在所有查询之前）。

注意，$ n $ 在类型 1 的查询后不会恢复到其初始值。

由于 Ognjen 害怕数论，Vasilije 向他保证在每次查询后 $ d(n) \le 10^9 $，但是即便有这个限制，他仍然需要你的帮助来解决这个问题。

**输入输出数据格式：**

**输入：**

第一行包含一个正整数 $ t $（$ 1 \le t \le 100 $）—— 测试用例的数量。

每个测试用例的第一行包含 2 个整数 $ n $ 和 $ q $（$ 1 \le n \le 10^6 $，$ 1 \le q \le 1000 $）—— 数 $ n $ 和查询的数量。

接下来的 $ q $ 行包含一个整数 $ k $（$ 1 \le k \le 2 $），如果 $ k=1 $ 则在这一行中还有一个整数 $ x $（$ 1 \le x \le 10^6 $）—— 查询的描述。

保证在给定的输入中，任何时刻 $ d(n) $ 都不会超过 $ 10^9 $。

保证所有测试用例的 $ q $ 之和不超过 $ 10^3 $。

**输出：**

对于每个类型 1 的查询，如果你能找到这样的正整数 $ a $ 使得 $ gcd(a, n) = 1 $ 且 $ d(n \cdot a) = n $，则输出 "YES"，否则输出 "NO"。

你可以以任何大小写形式输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的答案）。**题目大意：** Vasilije 是一位聪明的学生，他的离散数学老师 Sonja 非常擅长教授数论。他给了 Ognjen 一个正整数 $ n $。 定义 $ d(n) $ 为 $ n $ 的正整数因子的数量，定义 $ gcd(a, b) $ 为最大的整数 $ g $，使得 $ a $ 能被 $ g $ 整除且 $ b $ 也能被 $ g $ 整除。 之后，他给了 Ognjen $ q $ 个查询，查询类型有 2 种： 1. $ 1 $, $ x $ —— 将 $ n $ 设置为 $ n \cdot x $，然后回答以下问题：是否存在一个正整数 $ a $ 使得 $ gcd(a, n) = 1 $ 且 $ d(n \cdot a) = n $？ 2. $ 2 $ —— 将 $ n $ 重置为其初始值（在所有查询之前）。 注意，$ n $ 在类型 1 的查询后不会恢复到其初始值。 由于 Ognjen 害怕数论，Vasilije 向他保证在每次查询后 $ d(n) \le 10^9 $，但是即便有这个限制，他仍然需要你的帮助来解决这个问题。 **输入输出数据格式：** **输入：** 第一行包含一个正整数 $ t $（$ 1 \le t \le 100 $）—— 测试用例的数量。 每个测试用例的第一行包含 2 个整数 $ n $ 和 $ q $（$ 1 \le n \le 10^6 $，$ 1 \le q \le 1000 $）—— 数 $ n $ 和查询的数量。 接下来的 $ q $ 行包含一个整数 $ k $（$ 1 \le k \le 2 $），如果 $ k=1 $ 则在这一行中还有一个整数 $ x $（$ 1 \le x \le 10^6 $）—— 查询的描述。 保证在给定的输入中，任何时刻 $ d(n) $ 都不会超过 $ 10^9 $。 保证所有测试用例的 $ q $ 之和不超过 $ 10^3 $。 **输出：** 对于每个类型 1 的查询，如果你能找到这样的正整数 $ a $ 使得 $ gcd(a, n) = 1 $ 且 $ d(n \cdot a) = n $，则输出 "YES"，否则输出 "NO"。 你可以以任何大小写形式输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的答案）。