#include <bits/stdc++.h>
using namespace std;
int pm(int a, int e) {
  int r = 1;
  while (e) {
    if (e & 1) r = (1LL * r * a) % 1000000007;
    e >>= 1;
    a = (1LL * a * a) % 1000000007;
  }
  return r;
}
int f[100005], fi[100005];
int c(int n, int k) {
  if (k < 0 || k > n) return 0;
  return 1LL * f[n] * fi[k] % 1000000007 * fi[n - k] % 1000000007;
}
vector<int> p[100005];
int main() {
  f[0] = fi[0] = 1;
  for (int i = 1, ThxDem = 100005; i < ThxDem; ++i)
    f[i] = (1LL * f[i - 1] * i) % 1000000007, fi[i] = pm(f[i], 1000000007 - 2);
  for (int i = 2, ThxDem = 100005; i < ThxDem; ++i)
    if (!((int)p[i].size()))
      for (int j = i; j < 100005; j += i) p[j].push_back(i);
  int q;
  scanf("%d", &q);
  while (q--) {
    int n, f;
    scanf("%d%d", &n, &f);
    int r = 0;
    for (int m = 0, ThxDem = 1 << ((int)p[n].size()); m < ThxDem; ++m) {
      int d = 1, q = 0;
      for (int i = 0, ThxDem = ((int)p[n].size()); i < ThxDem; ++i)
        if (m & (1 << i)) d *= p[n][i], q ^= 1;
      int a = c(n / d - 1, f - 1);
      if (q)
        r += 1000000007 - a;
      else
        r += a;
      r %= 1000000007;
    }
    printf("%d\n", r);
  }
  return 0;
}
