原根

i64 qpow(i64 a, i64 b, i64 P, i64 res = 1) {
    while (b) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
i64 eulerPhi(i64 n) {
    i64 ans = n;
    for (int i = 2 ; 1LL * i * i <= n ; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        ans = ans / n * (n - 1);
    }
    return ans;
}
vector<i64> getFactors(i64 x) {
    vector<i64> res;
    for (int i = 1 ; 1LL * i * i <= x ; i++) {
        if (x % i == 0) {
            res.emplace_back(i);
            if (x != 1LL * i * i) {
                res.emplace_back(x / i);
            }
        }
    }
    if (x > 1) {
        res.push_back(x);
    }
    return res;
}
i64 getMinRoot(i64 x) {
    i64 phi = eulerPhi(x);
    auto factors = getFactors(phi);
    for (int i = 1 ; ; i++) {
        if (__gcd(1LL * i, x) != 1) {
            continue;
        }
        bool flag = true;
        for (auto &e : factors) {
            if (e != phi && qpow(i, e, x) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) return i;
    }
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
namespace EulerSieve {
    vector<int> prime, phi;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        phi.resize(n);
        phi[1] = 1;
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                phi[i] = i - 1;
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    phi[i * x] = phi[i] * x;
                    break;
                }
                phi[i * x] = phi[i] * phi[x];
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using namespace EulerSieve;
const int N = 1000005;
using EulerSieve::primeInit;
using EulerSieve::phi;
using EulerSieve::prime;
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
bool exist[N + 100];
void existInit() {
    exist[2] = exist[4] = true;
    int len = prime.size();
    for (int i = 1 ; i < len ; i++) {
        for (i64 j = prime[i] ; j <= N ; j *= prime[i]) {
            exist[j] = true;
            if (j * 2 <= N) {
                exist[j * 2] = true;
            }
        }
    }
}
vector<int> getFactors(int x) {
    vector<int> res;
    for (int i = 1 ; i * i <= x ; i++) {
        if (x % i == 0) {
            res.emplace_back(i);
            if (x != i * i) {
                res.emplace_back(x / i);
            }
        }
    }
    return res;
}
vector<int> getPrimativeRoots(int m) {
    if (!exist[m]) return {};
    int phis = phi[m], fst;
    auto factors = getFactors(phis);
    for (int i = 1 ; ; i++) {
        if (__gcd(i, m) != 1) {
            continue;
        }
        bool flag = true;
        for (auto &e : factors) {
            if (e != phis && qpow(i, e, m) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            fst = i;
            break;
        }
    }
    int cur = fst;
    vector<int> res;
    for (int i = 1 ; i <= phis ; i++) {
        if (__gcd(phis, i) == 1) {
            res.emplace_back(cur);
        }
        cur = cur * fst % m;
    }
    return res;
}
void solve() {
    int n, d;
    cin >> n >> d;
    auto res = getPrimativeRoots(n);
    sort(begin(res), end(res));
    cout << res.size() << "\n";
    for (int i = d ; i <= (int(res.size()) / d) * d ; i += d) {
        if (i - 1 >= 0 && i - 1 < res.size())
        cout << res[i - 1] << " ";
        else
        cout << 0 << " ";
    }
    cout << "\n";
}
int main() {
    primeInit(N);
    existInit();
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}