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;
struct di {
  int div1, div2;
};
struct divv {
  int divv1, divv2, divv3;
};
di a = {0, 0};
divv b = {0, 0, 0};
int n, t;
di f(int nr) {
  for (int d = 2; d * d <= nr; d++)
    if (nr % d == 0) {
      di x = {d, nr / d};
      return x;
    }
  return a;
}
divv esteprod(int nr) {
  for (int d = 2; d * d <= nr; d++) {
    if (nr % d == 0) {
      di x = f(d);
      if (x.div1 != 0 and x.div1 != x.div2 and x.div1 != nr / d and
          x.div2 != nr / d) {
        divv z = {x.div1, x.div2, nr / d};
        return z;
      }
      x = f(nr / d);
      if (x.div1 != 0 and x.div1 != x.div2 and x.div1 != d and x.div2 != d) {
        divv z = {x.div1, x.div2, d};
        return z;
      }
    }
  }
  return b;
}
int main() {
  cin >> t;
  for (int tt = 1; tt <= t; tt++) {
    cin >> n;
    divv z = esteprod(n);
    if (z.divv1 != 0) {
      cout << "YES" << endl;
      cout << z.divv1 << ' ' << z.divv2 << ' ' << z.divv3 << endl;
    } else
      cout << "NO" << endl;
  }
  return 0;
}