# include <cstdio>
# include <cstring>
# define int long long
using namespace std;
const int N = 1e5+10;
int T,n,f,hp,v[N],pri[N],ff[N],c[N],jie[N],ni[N],fff[N],tot,mo=1e9+7;
int kua(int x,int y){
	int yi = 1, nw = 1;
	while (y){
		if (y&yi) nw = nw*x%mo;
		x = x*x%mo; y >>= yi;
	}
	return nw;
}
void yu(){
	for (int i = 2; i <= 1e5; i++){
		if (!v[i]) v[i] = i,pri[++hp] = i,ff[i]=1;
		for (int j = 1; j <= hp; j++){
			if (pri[j]*i > 1e5) break;
			v[i*pri[j]] = pri[j]; ff[i*pri[j]] = ff[i]+1;
			if (i % pri[j] == 0) break;
		}
	}
}
int C(int nn,int pp){
	if (nn<pp) return 0;
	if (nn==pp) return 1;
	return jie[nn]*ni[nn-pp]%mo*ni[pp]%mo;
}
int sol(int x){
	int nww = 0;
	while (x!=1){
		nww = v[x];
		x /= nww;
		if (x % nww == 0) return 0;
	}
	return 1;
}
signed main(){
	int op;
	scanf("%lld",&T); yu();
	jie[0] = 1;
	for (int i = 1; i <= 100000; i++) jie[i] = i*jie[i-1]%mo;
	for (int i = 0; i <= 100000; i++) ni[i] = kua(jie[i],mo-2);
	for (int i = 2; i <= 100000; i++){
		fff[i] = sol(i); 
	}
	while (T--){
		memset(c,0,sizeof(c));
		scanf("%lld %lld",&n,&f);
		if (f == 1){
			if (n==1) printf("1\n");
			else printf("0\n");
		}
		else{
			tot = C(n-1,f-1);
			int d;
			for (d = 2; d * d < n; d++){
				if (n % d != 0) continue;
				c[ff[d]] = (c[ff[d]]+fff[d]*C(n/d-1,f-1))%mo;
				c[ff[n/d]]=(c[ff[n/d]]+ fff[n/d]*C(d-1,f-1))%mo;
			}
			if (d*d == n){
				c[ff[d]] = (c[ff[d]]+fff[d]*C(n/d-1,f-1))%mo;
			}
			for (int i = 1; i <= n; i++){
				op = i%2==1? -1 : 1;
				tot = (tot + op*c[i]%mo)%mo;
			}
			printf("%lld\n",(tot%mo+mo)%mo);
		}
	}
	return 0;
}
// 176 4

rt 容斥 Test8就TLE了

预处理部分应该没问题，Test1-7是正常的

然后下面复杂度是$O(T*sqrt(n))$ ，复杂度没问题，好像也没死循环的可能（？ 不知道哪里出问题了

CF评测记录