divizibilitate

Time limit: 1s Memory limit: 32MB Input: Output:

Task

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

  • 1 n1 \ n: Check if nn is prime or not. If nn is prime print YES, otherwise print NO.
  • 2 n2 \ n: Find how many divisors nn has - for example, if n=12n = 12, you will print 66 (11, 22, 33, 44, 66, 1212 are the divisors of 1212).
  • 3 n3 \ n: Find how many prime divisors nn has - for example, if n=21n = 21, you will print 22 (33 and 77 are its prime divisors).
  • 4 n4 \ n: Print the prime factorization nn has, with each factor written on a line, in ascending order of the prime factors - for example, if n=60n = 60, you will print on 33 separate lines 2 22 \ 2, 3 13 \ 1 and 5 15 \ 1.

Input data

On the first line of the input you have tt, the number of integers tested. On each of the following tt lines you will have pairs of type (tip,n)(tip, n), where tiptip is between 11 and 44, and nn is a positive integer between 11 and 10910^9.

Output data

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

Constraints and clarifications

  • 1≤t≤1 0001 \leq t \leq 1 \ 000
  • 1≤n≤1091 \leq n \leq 10^9
  • For tests worth 2020 points each, we will only have queries of types 11, 22, 33 respectively 44.

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

77 is a prime number.
1515's divisors are 11, 33, 55, 1515.
2424's prime divisors are 22 and 33.
10001000's prime factorization is 23â‹…532^3 \cdot 5^3.

Log in or sign up to be able to send submissions!