Problem: You are given one integer number n. Find three distinct integers a, b, c such that 2 ≤ a, b, c and a ⋅ b ⋅ 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 ≤ t ≤ 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 ≤ n ≤ 10^9).

Output

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

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

Example

Input


5
64
32
97
2
12345


Output


YES
2 4 8 
NO
NO
NO
YES
3 5 823 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int max6 = 1e6 + 6;
map<int, int> rem;
int e[max6], p[max6];
int main() {
  int tests;
  scanf("%d", &tests);
  for (int i = 1; i <= 1000000; ++i) e[i] = i;
  int sl = 0;
  for (int i = 2; i <= 1000000; ++i)
    if (e[i] == i) {
      p[++sl] = i;
      for (int j = 1; j * i <= 1000000; ++j) e[i * j] = i;
    }
  while (tests--) {
    int n;
    scanf("%d", &n);
    int _n = n;
    rem.clear();
    sl = 0;
    int j = 1;
    while (n > 1000000) {
      int t;
      while (p[j] <= n / p[j] && n % p[j] != 0) j++;
      if (p[j] > n / p[j])
        t = n;
      else
        t = p[j];
      while (n % t == 0) {
        rem[t]++;
        n = n / t;
      }
    }
    while (n > 1) {
      int p = e[n];
      rem[p]++;
      n = n / p;
    }
    auto v = rem.begin();
    int a = (*v).first;
    rem[a]--;
    int b = 1;
    bool ok = false;
    int c;
    while (b == 1 || b == a) {
      if ((*v).second == 0) {
        v++;
        if (v == rem.end()) break;
      }
      (*v).second--;
      b = b * (*v).first;
    }
    c = _n / (a * b);
    if (a >= 2 && b >= 2 && c >= 2)
      if (a != b && b != c && c != a) ok = true;
    if (ok) {
      cout << "YES\n";
      cout << a << " " << b << " " << c << "\n";
    } else
      cout << "NO\n";
  }
}