#include <bits/stdc++.h>
using namespace std;
const int mod = (int)(1e9 + 7);
int n, k, q, M, pn, p[200], l_p[100005];
long long res, first[100005], g[100005];
long long mod_pow(long long a, int b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long c(int n, int k) {
  long long res = g[k] * g[n - k] % mod;
  res = res * first[n] % mod;
  return res;
}
inline void rec(int pos, int val, bool odd) {
  if (val > M) return;
  if (pos == pn) {
    int nn = n / val;
    if (odd)
      res -= c(nn - 1, k - 1);
    else
      res += c(nn - 1, k - 1);
    return;
  }
  rec(pos + 1, val, odd);
  rec(pos + 1, val * p[pos], !odd);
}
int calc(int n, int k) {
  if (n == 1) return 1;
  if (k == 1) return 0;
  pn = 0, M = n / k;
  int nn = n, j;
  while (nn > 1) {
    j = l_p[nn];
    p[pn++] = j;
    while (nn % j == 0) nn /= j;
  }
  res = 0;
  rec(0, 1, 0);
  res %= mod;
  res = (res + mod) % mod;
  return res;
}
int main() {
  for (int i = 2; i <= 100000; ++i)
    if (!l_p[i]) {
      for (int j = i; j <= 100000; j += i)
        if (!l_p[j]) l_p[j] = i;
    }
  first[0] = 1;
  g[0] = 1;
  for (int i = 1; i <= 100000; ++i) {
    first[i] = first[i - 1] * i % mod;
    g[i] = mod_pow(first[i], mod - 2);
  }
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k);
    printf("%d\n", calc(n, k));
  }
  return 0;
}
