本题需要使用 Pollard-Rho 算法。

算法讲解

我们需要了解：

同余的性质：如果两个整数 $x, y$ 满足 $x \equiv y \pmod p$（即 $x$ 和 $y$ 除以 $p$ 的余数相同），那么它们的差 $(x - y)$ 一定是 $p$ 的倍数。

则 $\gcd(|x - y|, N)$ 的结果一定是 $p$ 的倍数。

∵ $p$ 是 $N$ 的因数，

∴ $N = k \cdot p$。

∵ $x \equiv y \pmod p$，

∴ $x - y = m \cdot p$。

令 $d = \gcd(|x - y|, N) = \gcd(m \cdot p, k \cdot p) = p \cdot \gcd(m, k)$。

当 $\gcd(m, k) = 1$ 时，那么 $d$ 就等于 $p$。

当 $\gcd(m, k) \neq 1$ 时，$d$ 是 $N$ 的一个非平凡因数。

---

假设 $N$ 的最小素因数是 $p$。我们在模 $p$ 的意义下随机选取数字，模 $p$ 的余数只有 $0, 1, 2, ..., p-1$ 共 $p$ 种可能。

根据生日悖论的数学推导：从 $p$ 个元素中随机抽取，大约只需要抽取 $\sqrt{p}$ 次，就有超过 50% 的概率出现两个相同的元素（即 $x_i \equiv x_j \pmod p$）。

因为 $p \le \sqrt{N}$，所以 $\sqrt{p} \le N^{\frac{1}{4}}$。 这意味着，我们平均只需要生成 $N^{\frac{1}{4}}$ 个数字，就能找到一对满足条件的 $(x_i, x_j)$ 。

我们不能真的用系统随机数，因为我们需要序列具有确定性和可重复性，以便进行数学推导。

我们定义一个简单的二次多项式函数：

$$f(x) = (x^2 + c) \bmod N$$

其中 $c$ 是一个常数（通常 $c \neq 0, -2$）。

我们从起点 $x_1$ 开始，不断迭代：

$$x_2 = f(x_1), \quad x_3 = f(x_2), \quad \dots, \quad x_{k+1} = f(x_k)$$

由于模 $N$ 的余数只有 $N$ 种，这个序列 $\{x_k\}$ 迟早会出现重复，从而进入循环。

如图，由于序列排列形成的形状酷似希腊字母 $\rho$ ，所以该算法得名 rho 。

如果 $x \equiv y \pmod p$，那么 $f(x) \equiv f(y) \pmod p$ 。 $f(x) - f(y) = (x^2+c) - (y^2+c) = x^2 - y^2 = (x-y)(x+y)$ 。因为 $p \mid (x-y)$，所以 $p \mid (f(x)-f(y))$。

这意味着：如果在取模 $N$ 下还没进环，但在取模 $p$ 下可能已经进环了。因此我们应该找取模 $p$ 下的环。我们可以使用 Floyd 判环法 或改进的 Brent 判环法 。

Floyd 判环法

设两个变量 $a$（慢指针）和 $b$（快指针）：

初始使 $a = b = x_1$。让 $a$ 每次走 1 步，即 $a = f(a)$ ，让 $b$ 每次走 2 步，即 $b = f(f(b))$ 。当 $a==b$ 时意味着我们成功找到环了。

这个算法 scy 曾经讲过，我就不讲太多了

Brent 判环法

floyd 方法每走一步都要算一次 $gcd$ ，而 $gcd$ 本身也有开销。Brent 方法让快指针按 $2^k$ 的步长跳跃，减少了迭代次数，比 Floyd 快约 24%。

倍增优化：

不是每一步都算 $\gcd$，而是先累积多步的差值乘积 $P = \prod |x_i - y_i| \bmod N$，每隔 $k$ 步（如 $k=128$）再算一次 $\gcd(P, N)$。这样把多次 $\gcd$ 合并成一次，进一步降低了常数复杂度。

代码

#include<bits/stdc++.h>
#define int __int128
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
const int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
template<typename T>inline void qr(T &x){
	int f=1;x=0;
	char c=getchar();
	for(;!isdigit(c);c=getchar())f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	x*=f;
}
template<typename T>inline void qw(T x){
	if(x<0)
		putchar('-'),x=-x;
	if(x/10)qw(x/10);
	putchar(x%10+'0');
}
inline int qpow(int a,int b,int m){
    int res=1;
    a%=m;
    for(;b;b>>=1,a=(a*a)%m)
        if(b&1)
			res=(res*a)%m;
    return res;
}
inline bool Is_prime(int x){ // Miller-Rabin素性测试
	if(x<2)return false;
	if(x<=37){
		for(int p:prime)if(x==p)return true;
		return false;
	}
	int d=x-1,s=0;
	while(!(d&1))d>>=1,s++;
	for(int y:prime){
		if(y>=x)break;
		int t=qpow(y,d,x);
		if(t==1||t==x-1)continue;
		bool flg=false;
		for(int j=1;j<=s;j++){
			t=t*t%x;
			if(t==x-1){
				flg=true;
				break;
			}
		}
		if(!flg)return false;
	}
	return true;
}
inline int f(int x,int c,int m){return (x*x%m+c)%m;} // 伪随机迭代函数
inline int rho(int n){ // Pollard-Rho找因数
    if(n==4)return 2;
	int c=rand();
    int x=f(rand(),c,n); // 慢指针
    int y=f(x,c,n);      // 快指针
    for(int m=1;;m=min(m<<1,(int)128)){ // 倍增批量GCD优化
    	if(x==y)break;   // 模n下相遇，探测失败
        int cnt=1;
        for(int i=0;i<m;i++){
            cnt=(cnt*abs(x-y))%n; // 累积差值乘积
            if(!cnt)break;
            x=f(x,c,n);       // 走1步
            y=f(f(y,c,n),c,n);// 走2步
        }
        int d=__gcd(cnt,n); // 批量求GCD
        if(d!=1)return d;   // 找到因数
    }
    return n; // 返回n表示失败
}
int ans;
inline void dfs(int n){ // 递归分解
    int d=rho(n);
    while(d==n)d=rho(n); // 失败则重试
    int d2=n/d;
    if(Is_prime(d))ans=max(ans,d);
    else dfs(d);
    if(Is_prime(d2))ans=max(ans,d2);
    else dfs(d2);
}
inline int ga(int x){ // 获取最大素因数
    if(Is_prime(x))return x;
    ans=0;
    dfs(x);
    return ans;
}
signed main(){
    srand(time(0));
    int q;
    qr(q);
    while(q--){
        int x;
        qr(x);
        vector<int>v;
        while(x!=1){ // 不断剥离最大素因数
            int p=ga(x);
            v.push_back(p);
            x/=p;
        }
        sort(v.begin(),v.end());
        qw(v.size());
        putchar(' ');
        for(int t:v){
        	qw(t);
			putchar(' ');
		}
        puts("");
    }
}