#1948. 简单的数学题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e7 + 10;

// 杜教筛相关变量
ll mu[MAXN], sum_mu[MAXN];
vector<int> primes;
bool is_composite[MAXN];

// 线性筛预处理
void init_mu() {
    fill(is_composite, is_composite + MAXN, false);
    mu[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (i * p >= MAXN) break;
            is_composite[i * p] = true;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }
    for (int i = 1; i < MAXN; i++) {
        sum_mu[i] = sum_mu[i - 1] + mu[i];
    }
}

// 杜教筛计算莫比乌斯函数前缀和
ll get_mu_sum(ll n) {
    if (n < MAXN) return sum_mu[n];
    static unordered_map<ll, ll> memo;
    if (memo.count(n)) return memo[n];
    ll res = 1;
    for (ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res -= (r - l + 1) * get_mu_sum(n / l);
    }
    return memo[n] = res;
}

// 主计算函数
pair<ll, ll> solve(ll n, ll m, ll p) {
    ll total = 0, sum_y = 0;
    for (ll d = 1; d * d <= m; d++) {
        ll x_max = n / d;
        if (x_max == 0) break;
        ll q = m / (d * d);
        if (q == 0) break;
        
        // 计算a的范围
        ll a_min = 1, a_max = x_max;
        ll current_sum = 0;
        for (ll k = 1; k * k <= q; k++) {
            if (q % k != 0) continue;
            ll val = k;
            ll cnt = (x_max / val) - (x_max / (val + 1));
            current_sum += cnt * mu[k] * k;
            
            if (k != q / k) {
                val = q / k;
                cnt = (x_max / val) - (x_max / (val + 1));
                current_sum += cnt * mu[val] * val;
            }
        }
        
        // 累加结果
        ll cnt_pairs = get_mu_sum(q);
        total += cnt_pairs;
        sum_y += current_sum;
    }
    return {total % p, sum_y % p};
}

int main() {
    init_mu();
    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        ll p;
        cin >> n >> m >> p;
        auto ans = solve(n, m, p);
        cout << ans.first << " " << ans.second << endl;
    }
    return 0;
}