#include <bits/stdc++.h>
long long ans, f[100010], i, tot, g[100010], a, b, c, n, j;
void exgcd(long long a, long long b, long long &x, long long &y) {
  long long t;
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, x, y);
  t = x;
  x = y;
  y = t - a / b * y;
}
long long cnt(int a, int b) {
  long long u, v, w, x, y;
  u = f[a];
  w = 1000000007;
  v = (f[b] * f[a - b]) % 1000000007;
  exgcd(v, w, x, y);
  x = (x % 1000000007 + 1000000007) % 1000000007;
  x = (x * u) % 1000000007;
  return x;
}
void dfs(long long x, long long y, long long z) {
  long long i;
  if (a / x - 1 < b - 1) return;
  if (z == 0)
    ans = (ans + cnt(a / x - 1, b - 1)) % 1000000007;
  else
    ans = (ans - cnt(a / x - 1, b - 1) + 1000000007) % 1000000007;
  for (i = y; i <= tot; i++)
    if (x * g[i] <= a) dfs(x * g[i], i + 1, 1 - z);
}
int main() {
  scanf("%I64d", &n);
  f[0] = 1;
  for (i = 1; i <= 100000; i++) f[i] = f[i - 1] * i % 1000000007;
  for (i = 1; i <= n; i++) {
    ans = 0;
    scanf("%I64d%I64d", &a, &b);
    c = a;
    tot = 0;
    for (j = 2; j <= sqrt(a); j++)
      if (c % j == 0) {
        tot++;
        g[tot] = j;
        while (c % j == 0) c = c / j;
      }
    if (c > 1) {
      tot++;
      g[tot] = c;
    }
    dfs(1, 1, 0);
    printf("%I64d\n", ans);
  }
}
