#include <bits/stdc++.h>
using namespace std;
long long fac[110000], ifac[110000];
int p[110000], np, flag[110000];
long long Pow(long long x, long long y) {
  if (y == 0) return 1;
  long long res = Pow(x, y / 2);
  res = res * res % 1000000007;
  if (y & 1) res = res * x % 1000000007;
  return res;
}
void prepare() {
  int i, j;
  fac[0] = 1;
  for (i = 1; i < 110000; i++) fac[i] = fac[i - 1] * i % 1000000007;
  for (i = 0; i < 110000; i++) ifac[i] = Pow(fac[i], 1000000007 - 2);
  for (i = 2; i < 110000; i++) {
    if (flag[i]) continue;
    flag[i] = i;
    p[np++] = i;
    if (i > 1000) continue;
    for (j = i * i; j < 110000; j += i) flag[j] = i;
  }
}
int f[20], a[20], nf;
int d[1000], val[1000], nd;
void make(int dp, int cur) {
  if (dp == nf) {
    d[nd++] = cur;
    return;
  }
  int i;
  for (i = 0; i <= a[dp]; i++) {
    make(dp + 1, cur);
    cur *= f[dp];
  }
}
int main() {
  int T, N, F, i, j, x;
  prepare();
  for (scanf("%d", &T); T--;) {
    scanf("%d%d", &N, &F);
    nf = 0;
    while (N > 1) {
      f[nf] = flag[N];
      a[nf] = 0;
      while (N % f[nf] == 0) N /= f[nf], a[nf]++;
      nf++;
    }
    nd = 0;
    make(0, 1);
    for (i = 0; i < nd; i++) val[i] = 0;
    for (i = 0; i < nd; i++) {
      if (d[i] < F) continue;
      x = fac[d[i] - 1] * (ifac[F - 1] * ifac[d[i] - F] % 1000000007) %
          1000000007;
      val[i] = (val[i] + x) % 1000000007;
      for (j = i + 1; j < nd; j++)
        if (d[j] % d[i] == 0)
          val[j] = (val[j] - val[i] + 1000000007) % 1000000007;
    }
    printf("%d\n", val[nd - 1]);
  }
  return 0;
}
