C. Product of Three Numbers Codeforces

 C. Product of Three Numbers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given one integer number n$n$. Find three distinct integers a,b,c$a,b,c$ such that 2≤a,b,c$2\le a,b,c$ and a⋅b⋅c=n$a\cdot b\cdot c=n$ or say that it is impossible to do it.

If there are several answers, you can print any.

You have to answer t$t$ independent test cases.

Input

The first line of the input contains one integer t$t$ (1≤t≤100$1\le t\le 100$) — the number of test cases.

The next n$n$ lines describe test cases. The i$i$-th test case is given on a new line as one integer n$n$ (2≤n≤109$2\le n\le {10}^9$).

Output

For each test case, print the answer on it. Print "NO" if it is impossible to represent n$n$ as a⋅b⋅c$a\cdot b\cdot c$ for some distinct integers a,b,c$a,b,c$ such that 2≤a,b,c$2\le a,b,c$.

Otherwise, print "YES" and any possible such representation.

Example

input

Copy

5
64
32
97
2
12345

output

Copy

YES
2 4 8 
NO
NO
NO
YES
3 5 823 

Solution

#include<bits/stdc++.h>
using namespace std;
 
#define vv vector<int> v;
 
 
 
 
int main(){
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
 
 
    int t;
    cin>>t;
    while(t--){
        // cout<<"value of t is:"<<t<<endl;
        int n;
        cin>>n;
        vector<int>v;
        if(n<24){
            cout<<"NO\n";
        }
        else{
            int a,b,c,k=0;
            int temp=n;
            for(int i=2; i*i<=n; i++){
                if(n%i==0){
                    if(k==0){
                        a=i;
                        n/=a;
                    }
                    else if(k==1){
                        b=i;
                    }
                    k++;
                }
                if(k==2){
                    break;
                }
            }
            c=temp/(a*b);
            if(k<2 || a==b || b==c || c==a || c<2){
                cout<<"NO\n";
            }
            else if(a!=b && b!=c && c!=a){
                
            cout<<"YES\n"<<a<<" "<<b<<" "<<c<<endl;
            }
             
            
            }
        }
    return 0;
}