#include <bits/stdc++.h>
using namespace std;
const int limite = 100001;
long long int modulo = 1e9 + 7;
long long int eleva(long long int b, long long int e) {
  if (e == 0) return 1;
  if (e % 2 == 0) return eleva(b * b % modulo, e / 2);
  return b * eleva(b * b % modulo, e / 2) % modulo;
}
long long int inverso(long long int x) { return eleva(x, modulo - 2); }
long long int fact[limite];
long long int invfact[limite];
long long int combi(long long int n, long long int k) {
  if (k < 0) return 0;
  if (n < k) return 0;
  return fact[n] * invfact[k] % modulo * invfact[n - k] % modulo;
}
int np;
int p[limite];
long long int calcula(int ip, int n, int k, int signo) {
  if (n < k) return 0;
  if (ip == np) return signo * combi(n - 1, k - 1);
  long long int sol = calcula(ip + 1, n, k, signo);
  if (n % p[ip] == 0)
    sol = (sol + calcula(ip + 1, n / p[ip], k, -signo)) % modulo;
  return sol;
}
int esprimo[limite];
int factor[limite];
int main() {
  ios::sync_with_stdio(false);
  fact[0] = 1;
  invfact[0] = 1;
  for (int i = 1; i < limite; i++) {
    fact[i] = (fact[i - 1] * i) % modulo;
    invfact[i] = inverso(fact[i]);
  }
  for (int i = 2; i < limite; i++) esprimo[i] = 1;
  for (int i = 2; i < limite; i++) {
    if (esprimo[i]) {
      factor[i] = i;
      for (int j = i + i; j < limite; j += i) {
        esprimo[j] = 0;
        factor[j] = i;
      }
    }
  }
  int casos;
  cin >> casos;
  for (int cas = 0; cas < casos; cas++) {
    int n, k;
    cin >> n >> k;
    int nn = n;
    np = 0;
    while (nn > 1) {
      int f = factor[nn];
      if (np == 0 or p[np - 1] != f) p[np++] = f;
      nn /= f;
    }
    cout << (calcula(0, n, k, 1) + modulo) % modulo << endl;
  }
}
