#ifdef SU1
//#define _GLIBCXX_DEBUG
#endif

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forl(i, n) for (int i = 1; i <= int(n); i++)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
#define pb(a) push_back(a)
#define mp(x, y) make_pair((x), (y))
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define ft first
#define sc second
#define x first
#define y second

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld PI = acosl(ld(-1));
const ld EPS = 1e-9;

const int N = 50 + 3;

map<int, li> ans[5];
li C[N][N];

li calc (int n, int k)
{
	if (ans[k].count(n)) return ans[k][n];
	
	int on = n;
	
	li res = 1;
	
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i != 0) continue;
		int deg = 0;
		while (n % i == 0) deg++, n /= i;
		res *= C[deg + k - 1][k - 1];
	}
	
	if (n > 1)
	{
		int deg = 1;
		res *= C[deg + k - 1][k - 1];
	}
	
	//cerr << on << ' ' << k << ' ' << res << endl;
	
	ans[k][on] = res;
	
	return res;
}

int n, k;

inline bool read()
{
	if (scanf("%d%d", &n, &k) != 2) return false;
	return true;
}

inline void solve()
{
	li ans = 0;
	
	if (k == 1) ans = n;
	else
	{
		forl(i, n) ans += calc(i, k);
	}
#ifdef SU1
	cout << ans << endl;
#else
	printf("%lld\n", ans);
#endif
}

int main()
{
#ifdef SU1
	assert(freopen("input.txt", "rt", stdin));
//	assert(freopen("output.txt", "wt", stdout));
#endif

	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(5);
	
	C[0][0] = 1;
	forl(i, N - 1) forn(j, i + 1)
	{
		C[i][j] = C[i - 1][j];
		if (j > 0) C[i][j] += C[i - 1][j - 1];
	}
	
	int testCount;
	cin >> testCount;
	
	forn(test, testCount)
	{
		assert(read());
		solve();
	}
	
#ifdef SU1
	cerr << "=== TIME : " << clock() << " ===" << endl;
#endif
	return 0;
}
