#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e18 + 7;
const long long mod = 1e9 + 7;
const double eps = 1e-7;
const double PI = 2 * acos(0.0);
const double E = 2.71828;
long long fact[100005], ifact[100005];
int cnt[100005];
long long inv(long long x) {
  long long n = mod - 2;
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
long long c(int n, int k) {
  long long res = fact[n];
  res = (res * ifact[k]) % mod;
  res = (res * ifact[n - k]) % mod;
  return res;
}
int n, f;
bool sq[100005];
int doit(int x) {
  if (x < f) return 0;
  return c(x - 1, f - 1);
}
void Solve() {
  scanf("%d %d", &n, &f);
  vector<int> divs;
  int res = 0;
  for (int i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      divs.push_back(i);
      if (n / i != i) divs.push_back(n / i);
    }
  }
  for (int(i) = 0; (i) < (divs.size()); ++(i)) {
    int cur = divs[i];
    if (sq[cur]) continue;
    int add = doit(n / cur);
    if (cnt[cur] & 1) add = mod - add;
    res = (res + add) % mod;
  }
  printf("%d\n", res);
}
int main(void) {
  fact[0] = 1;
  for (int i = 1; i < 100005; ++i) fact[i] = (fact[i - 1] * i) % mod;
  for (int i = 2; i < 100005; ++i) {
    if (!cnt[i]) {
      for (int j = i; j < 100005; j += i) {
        ++cnt[j];
      }
    }
  }
  for (int i = 2; i <= 2005; ++i)
    for (int j = i * i; j < 100005; j += i * i) {
      sq[j] = true;
    }
  for (int(i) = 0; (i) < (100005); ++(i)) ifact[i] = inv(fact[i]);
  int t;
  scanf("%d", &t);
  for (int(i) = 0; (i) < (t); ++(i)) Solve();
  return 0;
}
