#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100500, MOD = 1e9 + 7;
struct {
  int p, e;
} Fafa[10];
long long expmod(long long b, long long e) {
  if (!e) return 1;
  return (e % 2 ? b : 1) * expmod(b * b % MOD, e / 2) % MOD;
}
long long F[MAXN], FI[MAXN];
long long CMB(long long n, long long k) {
  if (k < 0) return 0;
  if (k > n) return 0;
  return (F[n] * FI[k] % MOD) * FI[n - k] % MOD;
}
void solve(int m, int k) {}
int n, k, q;
map<int, int> P;
int main() {
  F[0] = FI[0] = 1;
  for (int i = (int)1; i < (int)MAXN; i++) F[i] = F[i - 1] * i % MOD;
  for (int i = (int)1; i < (int)MAXN; i++)
    FI[i] = FI[i - 1] * expmod(i, MOD - 2) % MOD;
  int q;
  cin >> q;
  for (int cs = (int)0; cs < (int)q; cs++) {
    P.clear();
    scanf("%d %d", &n, &k);
    int p = 2;
    while (p * p <= n) {
      if (n % p)
        p++;
      else {
        if (!P.count(p))
          P[p] = 1;
        else
          P[p]++;
        ;
        n /= p;
      }
    }
    if (n > 1)
      if (!P.count(n))
        P[n] = 1;
      else
        P[n]++;
    ;
    int B = P.size();
    int x = 0;
    for (auto it = P.begin(); it != P.end(); ++it) {
      Fafa[x].p = (it->first);
      Fafa[x++].e = (it->second);
    }
    long long ans = 0;
    for (int v = (int)0; v < (int)1 << B; v++) {
      long long fact = 1;
      for (int i = (int)0; i < (int)B; i++)
        fact *= ((v & (1 << i)) ? expmod(Fafa[i].p, Fafa[i].e)
                                : -expmod(Fafa[i].p, Fafa[i].e - 1));
      if (fact >= 0)
        ans = (ans + CMB(fact - 1, k - 1)) % MOD;
      else
        ans = (ans - CMB(-fact - 1, k - 1)) % MOD;
    }
    printf("%lld\n", (ans + MOD) % MOD);
  }
}
