#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const long long mod = 1000000007;
vector<int> vp[N];
int miu[N];
long long jc[N], njc[N];
void add(long long &x, long long y, int f) {
  if (f == -1) y = mod - y;
  x += y;
  while (x >= mod) x -= mod;
}
long long sqrr(long long x) { return x * x % mod; }
long long ksm(long long x, long long y) {
  if (!y) return 1;
  if (y == 1) return x;
  if (y & 1) return sqrr(ksm(x, y / 2)) * x % mod;
  return sqrr(ksm(x, y / 2));
}
void init() {
  const int N = 100000;
  int i, j;
  for (i = 1; i <= N; i++)
    for (j = i; j <= N; j += i) vp[j].push_back(i);
  for (i = 2, miu[1] = 1; i <= N; i++) {
    int p = vp[i][1];
    if ((i / p) % p == 0)
      miu[i] = 0;
    else
      miu[i] = miu[i / p] * (-1);
  }
  for (i = 1, jc[0] = njc[0] = 1; i <= N; i++) {
    jc[i] = jc[i - 1] * i % mod;
    njc[i] = ksm(jc[i], mod - 2);
  }
}
long long cal(long long n, long long m) {
  if (n < m) return 0;
  return jc[n] * njc[m] % mod * njc[n - m] % mod;
}
int main() {
  init();
  int q;
  scanf("%d", &q);
  while (q--) {
    int i, n, m;
    long long ans = 0;
    scanf("%d%d", &n, &m);
    for (i = 0; i < vp[n].size(); i++) {
      if (miu[vp[n][i]] == 0) continue;
      int a = n / vp[n][i] - 1;
      long long g = cal(a, m - 1);
      add(ans, g, miu[vp[n][i]]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}
