#include <bits/stdc++.h>
using namespace std;
const int size = 100007;
const long long modulo = 1000000007;
const long long oo = 7e18;
const double EPS = 1e-13;
const double PI = acos(-1.0);
long long fact[size], rev_fact[size];
vector<long long> divisors[size];
long long used[size], dp[size];
int query = 0;
long long power(long long base, long long expo) {
  long long res = 1;
  while (expo > 0) {
    if (expo & 1) res = (res * base) % modulo;
    base = (base * base) % modulo;
    expo >>= 1;
  }
  return res;
}
long long C(long long n, long long k) {
  long long res = fact[n] * rev_fact[k];
  res %= modulo;
  res *= rev_fact[n - k];
  res %= modulo;
  return res;
}
long long f(long long n, long long k) {
  if (n < k || (k == 1 && n > 1))
    return 0;
  else if (n == k)
    return 1;
  else if (used[n] == query)
    return dp[n];
  else {
    used[n] = query;
    long long res = C(n - 1, k - 1);
    for (long long i = 0; i < divisors[n].size(); i++) {
      res = (res + modulo - f(divisors[n][i], k)) % modulo;
    }
    dp[n] = res;
    return res;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 2; i < size; i++)
    for (int j = 2 * i; j < size; j += i) divisors[j].push_back(i);
  fact[0] = 1;
  for (int i = 1; i < size; i++) {
    fact[i] = (fact[i - 1] * i) % modulo;
    rev_fact[i] = power(fact[i], modulo - 2);
  }
  int q;
  cin >> q;
  while (q--) {
    long long n, k;
    cin >> n >> k;
    ++query;
    cout << f(n, k) << endl;
  }
  return 0;
}
