#include <bits/stdc++.h>
using namespace std;
int fact[1000000], d[1000000], l;
inline int Pow_Log(int x, int p) {
  int sol = 1;
  while (p) {
    if (p & 1) {
      sol = (1LL * sol * x) % 1000000007;
      --p;
    }
    p >>= 1;
    x = (1LL * x * x) % 1000000007;
  }
  return sol;
}
inline int Comb(int n, int k) {
  int aux = (1LL * fact[n] * Pow_Log(fact[k], 1000000007 - 2)) % 1000000007;
  return (1LL * aux * Pow_Log(fact[n - k], 1000000007 - 2)) % 1000000007;
}
inline int Nr(int n, int k) {
  if (n < 0) return 0;
  return Comb(n + k - 1, k - 1);
}
inline void Diviz(int x) {
  l = 0;
  int k = 0;
  while (x % 2 == 0) {
    x >>= 1;
    ++k;
  }
  if (k) d[++l] = 2;
  int dd = 3;
  while (1LL * dd * dd <= x && x > 1) {
    k = 0;
    while (x % dd == 0) {
      ++k;
      x /= dd;
    }
    if (k) d[++l] = dd;
    dd += 2;
  }
  if (x > 1) d[++l] = x;
}
inline void Fix(int &x) {
  if (x >= 1000000007) x -= 1000000007;
  if (x < 0) x += 1000000007;
}
int main() {
  int n, f, i, j, Q, sol;
  cin.sync_with_stdio(0);
  cin >> Q;
  fact[0] = 1;
  for (i = 1; i <= 100000; ++i) fact[i] = (1LL * fact[i - 1] * i) % 1000000007;
  while (Q--) {
    cin >> n >> f;
    sol = Nr(n - f, f);
    Diviz(n);
    for (i = 1; i < (1 << l); ++i) {
      int nr = 0, prod = 1;
      for (j = 0; j < l; ++j)
        if ((1 << j) & i) {
          ++nr;
          prod *= d[j + 1];
        }
      if (nr & 1)
        sol -= Nr(n / prod - f, f);
      else
        sol += Nr(n / prod - f, f);
      Fix(sol);
    }
    cout << sol << "\n";
  }
  return 0;
}
