H. Hours in Class
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

AnaLu spent the whole day at LINF studying Number Theory, so she decided to put her new knowledge into practice! Because of that, when she got home, she went straight to her room to solve problems. Then, after many ACs, she ended up falling asleep. And she had a dream...

In this dream, AnaLu was once again a 6th-grade student, and the class of the day was about multiplication, exponentiation, and divisibility. The teacher wrote the following definitions on the board:

  1. Consider positive integers $$$A$$$ and $$$X$$$.
  2. $$$A \cdot X$$$: $$$A$$$ multiplied by $$$X$$$.
  3. $$$A ^ X$$$: $$$A$$$ raised to the power $$$X$$$ (which is the same as doing $$$A \cdot A \cdot A \cdot \ldots \cdot A$$$, with $$$X$$$ factors equal to $$$A$$$).
  4. $$$A | X$$$: means that $$$A$$$ divides $$$X$$$, that is, there exists some positive integer $$$B$$$ such that $$$A \cdot B = X$$$.

But, not satisfied, the teacher decided to challenge her students. She asked each one to keep in their notebook the value of the number $$$A$$$, which initially is equal to $$$1$$$. The teacher will make $$$Q$$$ queries about this number $$$A$$$, in which a number $$$X$$$ will be written on the board and all students must either update the value of $$$A$$$ accordingly or answer a question, depending on the type of the query. There are three types:

  1. All students must update the value of $$$A$$$ to $$$A = A \cdot X$$$ in their notebook.
  2. All students must update the value of $$$A$$$ to $$$A = A^X$$$ in their notebook.
  3. All students must answer (in English, with "Yes" or "No"): $$$X|A$$$?

AnaLu then realized that she was in a dream, since, depending on the teacher's queries, the number $$$A$$$ could become so large that it would be impossible to write it down even if all the notebooks in the universe were put together. Even so, she realized that it would still be possible to answer the teacher's divisibility queries (type $$$3$$$) correctly with the help of a computer.

But AnaLu did not bring any computer into the dream, so you must help her answer the queries!

Input

The first line contains an integer $$$Q$$$ $$$(1 \le Q \le 10^5)$$$, the number of queries.

The next $$$Q$$$ lines contain two integers $$$t$$$ $$$(1 \le t \le 3)$$$ and $$$X$$$ $$$(2 \le X \le 10^5)$$$, the type of the query and its parameter. It is guaranteed that there is at least one query of type 3.

Output

For each query of type $$$3$$$, print a line with the answer to that query: "Yes" if $$$X$$$ is a divisor of $$$A$$$, or "No" otherwise.

Example
Input
6
2 100000
1 3
2 3
1 2
3 12
3 18
Output
No
Yes
Note

Explanation of the example:

Initially, $$$A = 1$$$.

After the first query, $$$A = 1^{100000} = 1$$$.

After the second query, $$$A = 1 \cdot 3 = 3$$$.

After the third query, $$$A = 3^3 = 27$$$.

After the fourth query, $$$A = 27 \cdot 2 = 54$$$.

For the fifth query, $$$12$$$ does not divide $$$A$$$, so the answer to the query is "No".

For the sixth query, $$$18$$$ divides $$$A$$$, so the answer to the query is "Yes".