OI VIII - gol (Alt2)

// https://szkopul.edu.pl/problemset/problem/B8uHcsCWL_20NSJij1AL1b4C/site/?key=statement

#include <iostream>

using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

bool is_prime(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    static const long long bases[] = {2, 7, 61};
    for (long long a : bases) {
        if (n <= a) break;
        long long x = power(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = (x * x) % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

void solve() {
    long long n;
    cin >> n;

    if (n % 2 != 0 && is_prime(n)) {
        cout << 1 << "\n" << n << "\n";
    } else if (n % 2 == 0) {
        for (long long p1 = 3; p1 <= n / 2; p1 += 2) {
            if (is_prime(p1)) {
                long long p2 = n - p1;
                if (p2 > p1 && is_prime(p2)) {
                    cout << 2 << "\n" << p1 << " " << p2 << "\n";
                    return;
                }
            }
        }
    } else {
        for (long long p1 = 3; p1 <= n / 3; p1 += 2) {
            if (!is_prime(p1)) continue;
            for (long long p2 = p1 + 2; p2 <= (n - p1) / 2; p2 += 2) {
                if (!is_prime(p2)) continue;
                long long p3 = n - p1 - p2;

                if (p3 > p2 && is_prime(p3)) {
                    cout << 3 << "\n" << p1 << " " << p2 << " " << p3 << "\n";
                    return;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}