# 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$. Find three distinct integers $a,b,c$ such that $2\le a,b,c$ and $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$ independent test cases.

Input

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

The next $n$ lines describe test cases. The $i$-th test case is given on a new line as one integer $n$ ($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$ as $a\cdot b\cdot c$ for some distinct integers $a,b,c$ such that $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;}