Ta có thể nhận xét rằng, nếu ~m \nmid n~, thì không thể có cách nào để biến ~n~ thành ~m~. Do đó, ta sẽ in ra -1.

Ngược lại, để tìm được sô thao tác nhỏ nhất, mỗi bước ta chỉ cần làm như sau đến khi ~n = m~:

• Đặt ~k = \frac{m}{n}~.
• Nếu ~t = gcd(n,k)~ là ~1~ mà ~n < m~ thì không thể biến đổi được ~n~ thành ~m~. Ngược lại thì ta thực hiện thao tác: nhân ~n~ với ~t~.

Thuật toán trên dựa vào điều kiện, bản chất ta cần biến các số mũ trong phân tích thừa số nguyên tố của ~n~ thành các số mũ trong phân tích thừa số nguyên tố của ~m~.

Vậy nên, giá trị ~\frac{m}{n}~ chính là phần tử của phân tích thừa số nguyên tố của ~m~ mà không có trong phân tích thừa số nguyên tố của ~n~. Do phép toán bị bao bởi cận về ước chung lớn nhất, vậy nên ở mỗi thao tác, số mũ tối đa có thể thêm cho mỗi thừa số nguyên tố là nhân đôi.

Dễ thấy cách làm này đạt được cận tối đa đó, và sẽ cho ra kết quả tốn ít thao tác nhất.

#include<bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> ans;
    bool ok = m >= n;
    while (n < m) {
        if (m % n) {
            ok = false;
            break;
        } 
        int t = __gcd(n, m/n);
        if (t == 1) {
            ok = false;
            break;
        }
        n *= t;
        ans.push_back(t);
    }
    if (ok) {
        cout << (int) ans.size();
        for (auto u : ans) {
            cout << ' ' << u;
        }
        cout << '\n';
    } else cout << -1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}