#include <bits/stdc++.h>
using namespace std;
const int N = 100500;
const int mod = 1000000007;
long long binpow(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = (ret * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ret;
}
long long f[N], inv[N];
long long get(int n, int k) {
  if (n < k) return 0;
  long long ret = f[n];
  ret = (ret * inv[n - k]) % mod;
  ret = (ret * inv[k]) % mod;
  return ret;
}
int lp[N], pr[N], sz = 0, M[N];
int t, n, k;
long long ans = 0;
void calc(int d) {
  ans += (get(n / d - 1, k - 1) * 1ll * M[d]) % mod;
  if (ans > mod) ans -= mod;
  if (ans < 0) ans += mod;
}
int main() {
  f[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= 100000; ++i) {
    f[i] = (f[i - 1] * i) % mod;
    inv[i] = binpow(f[i], mod - 2);
  }
  lp[0] = 1;
  lp[1] = 1;
  for (int i = 2; i <= 100000; ++i) {
    if (!lp[i]) {
      lp[i] = i;
      pr[++sz] = i;
    }
    for (int j = 1; j <= sz && pr[j] <= lp[i]; ++j) {
      if (pr[j] * 1ll * i > 100000) break;
      lp[pr[j] * i] = pr[j];
    }
  }
  M[1] = 1;
  for (int i = 2; i <= 100000; ++i) {
    int tt = 0;
    int x = i;
    int last = 0;
    bool ok = 1;
    while (x > 1) {
      if (last == lp[x]) {
        ok = 0;
        break;
      }
      last = lp[x];
      x /= lp[x];
      ++tt;
    }
    if (!ok) {
      M[i] = 0;
    } else {
      if (tt & 1)
        M[i] = -1;
      else
        M[i] = 1;
    }
  }
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    ans = 0;
    for (int i = 1; i * i <= n; ++i) {
      if (n % i == 0) {
        calc(i);
        if (n / i != i) calc(n / i);
      }
    }
    printf("%I64d\n", (ans % mod + mod) % mod);
  }
  return 0;
}
