#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
long long int fact[maxn * 2 + 1];
long long int ifact[maxn * 2 + 1];
int n, f;
long long int fastex(long long int a, long long int b) {
  long long int ret = 1;
  while (b) {
    if (b & 1) {
      ret = (ret * a) % 1000000007;
    }
    a = (a * a) % 1000000007;
    b = b / 2;
  }
  return ret;
}
long long int ways(int n1, int k) {
  return (fact[n1 + k - 1] * ((ifact[n1 - 1] * ifact[k]) % 1000000007)) %
         1000000007;
}
vector<long long int> primes;
long long int inex() {
  long long int ret = 0;
  for (int i = 1; i < 1 << primes.size(); i++) {
    if (__builtin_popcount(i) % 2) {
      long long int fact = 1;
      for (int j = 0; j < primes.size(); j++) {
        if (i & (1 << j)) {
          fact *= primes[j];
        }
      }
      if ((n / fact - f) >= 0) ret = (ret + ways(f, n / fact - f)) % 1000000007;
    } else {
      long long int fact = 1;
      for (int j = 0; j < primes.size(); j++) {
        if (i & (1 << j)) {
          fact *= primes[j];
        }
      }
      if ((n / fact - f) >= 0)
        ret = (ret + 1000000007 - ways(f, n / fact - f)) % 1000000007;
    }
  }
  return ret % 1000000007;
}
int main() {
  int cases;
  cin >> cases;
  fact[0] = 1;
  ifact[0] = fastex(1, 1000000007 - 2);
  for (int i = 1; i <= maxn * 2; i++) {
    fact[i] = (fact[i - 1] * i) % 1000000007;
    ifact[i] = fastex(fact[i], 1000000007 - 2) % 1000000007;
  }
  while (cases--) {
    cin >> n >> f;
    int m = n;
    for (int i = 2; i <= m / i; i++) {
      if (m % i == 0) {
        while (m % i == 0) m /= i;
        primes.push_back(i);
      }
    }
    if (m != 1) primes.push_back(m);
    cout << (ways(f, n - f) + 1000000007 - inex()) % 1000000007 << endl;
    primes.clear();
  }
  return 0;
}
