Task

You are given $t$ and $t$ positive integers. For each of the integers, you will have to answer a question of one of the following types:

• $1 \ n$: Check if $n$ is prime or not. If $n$ is prime print YES, otherwise print NO.
• $2 \ n$: Find how many divisors $n$ has - for example, if $n = 12$, you will print $6$ ($1$, $2$, $3$, $4$, $6$, $12$ are the divisors of $12$).
• $3 \ n$: Find how many prime divisors $n$ has - for example, if $n = 21$, you will print $2$ ($3$ and $7$ are its prime divisors).
• $4 \ n$: Print the prime factorization $n$ has, with each factor written on a line, in ascending order of the prime factors - for example, if $n = 60$, you will print on $3$ separate lines $2 \ 2$, $3 \ 1$ and $5 \ 1$.

Input data

On the first line of the input you have $t$, the number of integers tested. On each of the following $t$ lines you will have pairs of type $(tip, n)$, where $tip$ is between $1$ and $4$, and $n$ is a positive integer between $1$ and $10^9$.

Output data

For each of the $t$ questions we will print the answer according to the presented format.

Constraints and clarifications

• $1 \leq t \leq 1 \ 000$
• $1 \leq n \leq 10^9$
• For tests worth $20$ points each, we will only have queries of types $1$, $2$, $3$ respectively $4$.

Example

stdin

8
1 7
2 15
3 24
4 1000
1 5835834
2 7675774
3 30240
4 14400

stdout

YES
4
2
2 3
5 3
NO
8
4
2 6
3 2
5 2

Explanation

$7$ is a prime number.
$15$'s divisors are $1$, $3$, $5$, $15$.
$24$'s prime divisors are $2$ and $3$.
$1000$'s prime factorization is $2^3 \cdot 5^3$.