#include <bits/stdc++.h>
using namespace std;
const int size = 111111;
long long mod = 1000000007;
int n, q, f;
long long ans[size];
int a[size], num;
long long jc[size], r[size];
long long mul(long long a, int p) {
  if (p == 0) return 1;
  if (p == 1) return a;
  long long x = mul(a, p / 2);
  x = (x * x) % mod;
  if (p & 1) x = (x * a) % mod;
  return x;
}
long long divv(int p, int f) {
  if (f > p) return 0;
  long long x = jc[p - 1] * r[f - 1] % mod;
  x = (x * r[p - f]) % mod;
  return x;
}
int main() {
  cin >> q;
  jc[0] = 1;
  r[0] = 1;
  for (int i = 1; i < size; i++) {
    jc[i] = (jc[i - 1] * i % mod);
    r[i] = mul(jc[i], mod - 2);
  }
  while (q--) {
    cin >> n >> f;
    int m = n;
    num = 0;
    for (int i = 2; i * i <= m; i++)
      if (m % i == 0) {
        a[num++] = i;
        while (m % i == 0) m /= i;
      }
    if (m > 1) a[num++] = m;
    sort(a, a + num);
    long long res = 0;
    for (int i = 0; i < (1 << num); i++) {
      int ct = 0, tmp = 1;
      for (int j = 0; j < num; j++)
        if (i & (1 << j)) {
          ct++;
          tmp *= a[j];
        }
      ans[i] = divv(n / tmp, f);
      if (ct & 1) ans[i] *= -1;
      res = (res + ans[i]) % mod;
      res = (res + mod) % mod;
    }
    cout << res << endl;
  }
}
