#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <unordered_map>
#include <list>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<double, int> Pdi;
typedef tuple<int, int, int> Ti;
typedef tuple<int, int, ll> Tiil;
typedef tuple<ll, int, int> Tlii;
typedef tuple<ll, ll, int> Tlli;
#define Fi first
#define Se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define rep(pos, len) for(int pos=0;pos<len;pos++)
#define repp(pos, len) for(int pos=1;pos<=len;pos++)
#define all(x) x.begin(), x.end()
#define ABS(x) (((x) > 0 ) ? (x) : (-(x)))
#define MAX2(x, y) (((x) > (y)) ? (x) : (y))
#define MIN2(x, y) (((x) < (y)) ? (x) : (y))
#define MAX3(x, y, z) ( (x) > (y) ? ( (x) > (z) ? (x) : (z) ) : ( (y) > (z) ? (y) : (z) ) )
#define MIN3(x, y, z) ( (x) < (y) ? ( (x) < (z) ? (x) : (z) ) : ( (y) < (z) ? (y) : (z) ) )
#define MID3(val1,val2,val3) MAX2(MIN2(MAX2(val1,val2),val3),MIN2(val1,val2))
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)
#define getll1(X) scanf("%lld",&X)
#define getll2(X,Y) scanf("%lld%lld",&X,&Y)
#define getll3(X,Y,Z) scanf("%lld%lld%lld",&X,&Y,&Z)
#define getll4(X,Y,Z,W) scanf("%lld%lld%lld%lld",&X,&Y,&Z,&W)
#define getll(...) GET_MACRO(__VA_ARGS__, getll4, getll3, getll2, getll1) (__VA_ARGS__)
#define dout(n) printf("%d\n",n)
#define lldout(n) printf("%lld\n",n)
// 1-index
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define INF 987654321
#define IINF 98765432198765432
#define MOD 1000000007
const int MAXN = 1e5 + 50;
ll fact[MAXN], finv[MAXN]; // fact[n] = n!, finv[MAXN] = (n!)^(-1)
bool vis[MAXN];
vector<int> pfactor[MAXN];
ll inverse(ll a, ll m) {
ll m0 = m, t, q;
ll x0 = 0, x1 = 1;
if (m == 1)
return 0;
while (a > 1) {
// q is quotient
q = a / m;
t = m;
// m is remainder now, process same as
// Euclid's algo
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// Make x1 positive
if (x1 < 0)
x1 += m0;
return x1;
}
ll c(int n, int k) {
return (((fact[n] * finv[k]) % MOD) * finv[n-k]) % MOD;
}
void findPrime() {
for(int n = 2; n <= 1e5; n++) {
if(vis[n]) continue;
vis[n] = true;
for(int k = 1; k * n <= 1e5; k++) {
vis[k * n] = true;
pfactor[k * n].pb(n);
}
}
}
void init() {
fact[0] = 1;
repp(n, 1e5) fact[n] = (fact[n-1] * n) % MOD;
finv[0] = 1;
repp(n, 1e5) finv[n] = inverse(fact[n], MOD);
}
int main() {
init();
findPrime();
int T;
geti(T);
while(T--) {
int n, f;
geti(n, f);
ll ans = 0;
for(int mask = 0; mask < (1 << pfactor[n].size()); mask++) {
int cnt = 0;
int tmp = n;
rep(i, pfactor[n].size()) {
if((mask >> i) & 1) {
tmp /= pfactor[n][i];
cnt++;
}
}
if(cnt & 1) {
ans = (ans - c(tmp - 1, f - 1) + MOD) % MOD;
} else {
ans = (ans + c(tmp - 1, f - 1)) % MOD;
}
}
printf("%lld\n", ans);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxtZW1vcnkuaD4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPGFzc2VydC5oPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDx1bm9yZGVyZWRfbWFwPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPHRpbWUuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IFBpOwp0eXBlZGVmIHBhaXI8bGwsIGxsPiBQbGw7CnR5cGVkZWYgcGFpcjxsbCwgaW50PiBQbGk7CnR5cGVkZWYgcGFpcjxpbnQsIGxsPiBQaWw7CnR5cGVkZWYgcGFpcjxkb3VibGUsIGludD4gUGRpOwp0eXBlZGVmIHR1cGxlPGludCwgaW50LCBpbnQ+IFRpOwp0eXBlZGVmIHR1cGxlPGludCwgaW50LCBsbD4gVGlpbDsKdHlwZWRlZiB0dXBsZTxsbCwgaW50LCBpbnQ+IFRsaWk7CnR5cGVkZWYgdHVwbGU8bGwsIGxsLCBpbnQ+IFRsbGk7CgojZGVmaW5lIEZpIGZpcnN0CiNkZWZpbmUgU2Ugc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgbXQgbWFrZV90dXBsZQojZGVmaW5lIHJlcChwb3MsIGxlbikgZm9yKGludCBwb3M9MDtwb3M8bGVuO3BvcysrKQojZGVmaW5lIHJlcHAocG9zLCBsZW4pIGZvcihpbnQgcG9zPTE7cG9zPD1sZW47cG9zKyspCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQoKI2RlZmluZSBBQlMoeCkgKCgoeCkgPiAwICkgPyAoeCkgOiAoLSh4KSkpCiNkZWZpbmUgTUFYMih4LCB5KSAoKCh4KSA+ICh5KSkgPyAoeCkgOiAoeSkpCiNkZWZpbmUgTUlOMih4LCB5KSAoKCh4KSA8ICh5KSkgPyAoeCkgOiAoeSkpCiNkZWZpbmUgTUFYMyh4LCB5LCB6KSAoICh4KSA+ICh5KSAgPyAoICh4KSA+ICh6KSA/ICh4KSA6ICh6KSAgKSA6ICggKHkpID4gKHopID8gKHkpIDogKHopICkgICkKI2RlZmluZSBNSU4zKHgsIHksIHopICggKHgpIDwgKHkpICA/ICggKHgpIDwgKHopID8gKHgpIDogKHopICApIDogKCAoeSkgPCAoeikgPyAoeSkgOiAoeikgKSAgKQojZGVmaW5lIE1JRDModmFsMSx2YWwyLHZhbDMpIE1BWDIoTUlOMihNQVgyKHZhbDEsdmFsMiksdmFsMyksTUlOMih2YWwxLHZhbDIpKQoKI2RlZmluZSBHRVRfTUFDUk8oXzEsXzIsXzMsXzQsTkFNRSwuLi4pIE5BTUUKCiNkZWZpbmUgZ2V0aTEoWCkgc2NhbmYoIiVkIiwmWCkKI2RlZmluZSBnZXRpMihYLFkpIHNjYW5mKCIlZCVkIiwmWCwmWSkKI2RlZmluZSBnZXRpMyhYLFksWikgc2NhbmYoIiVkJWQlZCIsJlgsJlksJlopCiNkZWZpbmUgZ2V0aTQoWCxZLFosVykgc2NhbmYoIiVkJWQlZCVkIiwmWCwmWSwmWiwmVykKI2RlZmluZSBnZXRpKC4uLikgR0VUX01BQ1JPKF9fVkFfQVJHU19fLCBnZXRpNCwgZ2V0aTMsIGdldGkyLCBnZXRpMSkgKF9fVkFfQVJHU19fKQoKI2RlZmluZSBnZXRsbDEoWCkgc2NhbmYoIiVsbGQiLCZYKQojZGVmaW5lIGdldGxsMihYLFkpIHNjYW5mKCIlbGxkJWxsZCIsJlgsJlkpCiNkZWZpbmUgZ2V0bGwzKFgsWSxaKSBzY2FuZigiJWxsZCVsbGQlbGxkIiwmWCwmWSwmWikKI2RlZmluZSBnZXRsbDQoWCxZLFosVykgc2NhbmYoIiVsbGQlbGxkJWxsZCVsbGQiLCZYLCZZLCZaLCZXKQojZGVmaW5lIGdldGxsKC4uLikgR0VUX01BQ1JPKF9fVkFfQVJHU19fLCBnZXRsbDQsIGdldGxsMywgZ2V0bGwyLCBnZXRsbDEpIChfX1ZBX0FSR1NfXykKCiNkZWZpbmUgZG91dChuKSBwcmludGYoIiVkXG4iLG4pCiNkZWZpbmUgbGxkb3V0KG4pIHByaW50ZigiJWxsZFxuIixuKQoKLy8gMS1pbmRleAojZGVmaW5lIEwoeCkgKCh4KTw8MSkKI2RlZmluZSBSKHgpICgoKHgpPDwxKSsxKQoKI2RlZmluZSBJTkYgOTg3NjU0MzIxCiNkZWZpbmUgSUlORiA5ODc2NTQzMjE5ODc2NTQzMgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3Cgpjb25zdCBpbnQgTUFYTiA9IDFlNSArIDUwOwoKbGwgZmFjdFtNQVhOXSwgZmludltNQVhOXTsJLy8gZmFjdFtuXSA9IG4hLCBmaW52W01BWE5dID0gKG4hKV4oLTEpCmJvb2wgdmlzW01BWE5dOwp2ZWN0b3I8aW50PiBwZmFjdG9yW01BWE5dOwoKbGwgaW52ZXJzZShsbCBhLCBsbCBtKSB7CiAgICBsbCBtMCA9IG0sIHQsIHE7CiAgICBsbCB4MCA9IDAsIHgxID0gMTsKIAogICAgaWYgKG0gPT0gMSkKICAgICAgcmV0dXJuIDA7CiAKICAgIHdoaWxlIChhID4gMSkgewogICAgICAgIC8vIHEgaXMgcXVvdGllbnQKICAgICAgICBxID0gYSAvIG07CiAgICAgICAgdCA9IG07CiAKICAgICAgICAvLyBtIGlzIHJlbWFpbmRlciBub3csIHByb2Nlc3Mgc2FtZSBhcwogICAgICAgIC8vIEV1Y2xpZCdzIGFsZ28KICAgICAgICBtID0gYSAlIG0sIGEgPSB0OwogICAgICAgIHQgPSB4MDsKICAgICAgICB4MCA9IHgxIC0gcSAqIHgwOwogICAgICAgIHgxID0gdDsKICAgIH0KIAogICAgLy8gTWFrZSB4MSBwb3NpdGl2ZQogICAgaWYgKHgxIDwgMCkKICAgICAgIHgxICs9IG0wOwogICAgcmV0dXJuIHgxOwp9CgoKbGwgYyhpbnQgbiwgaW50IGspIHsKCXJldHVybiAoKChmYWN0W25dICogZmludltrXSkgJSBNT0QpICogZmludltuLWtdKSAlIE1PRDsKfQoKCgp2b2lkIGZpbmRQcmltZSgpIHsKCWZvcihpbnQgbiA9IDI7IG4gPD0gMWU1OyBuKyspIHsKCQlpZih2aXNbbl0pIGNvbnRpbnVlOwoJCXZpc1tuXSA9IHRydWU7CgkJZm9yKGludCBrID0gMTsgayAqIG4gPD0gMWU1OyBrKyspIHsKCQkJdmlzW2sgKiBuXSA9IHRydWU7CgkJCXBmYWN0b3JbayAqIG5dLnBiKG4pOwoJCX0KCX0KfQoKdm9pZCBpbml0KCkgewoJZmFjdFswXSA9IDE7CglyZXBwKG4sIDFlNSkgZmFjdFtuXSA9IChmYWN0W24tMV0gKiBuKSAlIE1PRDsKCWZpbnZbMF0gPSAxOwoJcmVwcChuLCAxZTUpIGZpbnZbbl0gPSBpbnZlcnNlKGZhY3Rbbl0sIE1PRCk7Cn0KCmludCBtYWluKCkgewoJaW5pdCgpOwoJZmluZFByaW1lKCk7CgoJaW50IFQ7CglnZXRpKFQpOwoJd2hpbGUoVC0tKSB7CgkJaW50IG4sIGY7CgkJZ2V0aShuLCBmKTsKCQlsbCBhbnMgPSAwOwoJCWZvcihpbnQgbWFzayA9IDA7IG1hc2sgPCAoMSA8PCBwZmFjdG9yW25dLnNpemUoKSk7IG1hc2srKykgewoJCQlpbnQgY250ID0gMDsKCQkJaW50IHRtcCA9IG47CgkJCXJlcChpLCBwZmFjdG9yW25dLnNpemUoKSkgewoJCQkJaWYoKG1hc2sgPj4gaSkgJiAxKSB7CgkJCQkJdG1wIC89IHBmYWN0b3Jbbl1baV07CgkJCQkJY250Kys7CgkJCQl9CgkJCX0KCQkJaWYoY250ICYgMSkgewoJCQkJYW5zID0gKGFucyAtIGModG1wIC0gMSwgZiAtIDEpICsgTU9EKSAlIE1PRDsKCQkJfSBlbHNlIHsKCQkJCWFucyA9IChhbnMgKyBjKHRtcCAtIDEsIGYgLSAxKSkgJSBNT0Q7CgkJCX0KCQl9CgoJCXByaW50ZigiJWxsZFxuIiwgYW5zKTsKCX0KfQ==