Divisor Sum

#include<bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define clr(x) vector<int>().swap(x);
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vector<int>>
#define vii vector<pii>
#define random mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnd(time(0));
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define le v * 2
#define re v * 2 + 1
#define tm (tl + tr) / 2
#define no {cout << "NO" << endl; return;}
#define yes {cout << "YES" << endl; return;}
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
const ll INF=9e18;
const ll MN=-2e9;
const ll MX=1e6+9;
const ll MXX=2e9;
const ll SQ=6e2;
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll PP=1e6+3;
const ll P2=1299827;
const ld PI=3.141592653589793;
const ld eps=1e-11;
typedef tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
    ordered_set;

int mul(int x, int y) {
    return (ll) x * y % MOD;
}

int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    return x;
}

int sub(int x, int y) {
    x -= y;
    if (x < 0) x += MOD;
    return x;
}

int fast(int x, ll y = MOD - 2) {
    if (!y) return 1;
    int res = fast(x, y / 2);
    res = mul(res, res);
    if (y & 1) res = mul(res, x);
    return res;
}

int C(ll n, int k) {
    if (!k) return 1;
    int res = C(n - 1, k - 1);
    res = mul(res, n % MOD);
    res = mul(res, fast(k));
    return res;
}

int p[MX];

void sieve() {
    for (int i=2; i<MX; i++) if (!p[i]) {
        for (int j=i; j<MX; j+=i) {
            p[j] = (p[j] ? p[j] : i);
        }
    }
}

int n, ans, dp[MX];
ll k;

int solve(int n) {
    if (n == 1) return 1;
    if (dp[n] != -1) return dp[n];
    int res = 0;
    int a = 0;
    int m = 1;
    int q = p[n];
    while (!(n % q)) {
        a += 1;
        n /= q;
        m *= q;
    }
    int d = m;
    for (int i=0; i<=a; i++) {
        res = add(res, mul(d, C(k - 1 + i, i)));
        d /= q;
    }
    res = mul(res, solve(n));
    return dp[n * m] = res;
}

void solve() {
    cin >> n >> k;
    ans = 0;
    for (int i=1; i<=n; i++) {
        dp[i] = -1;
    }
    for (int i=1; i<=n; i++) {
        ans = add(ans, solve(i));
    }
    cout << ans << endl;
}

int main() {
    FAST;
    sieve();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

/*



*/