题意：给你一个n，m问你1-n里面(x)有多少对gcd(x, n)>=m。
思路：我们可以设n=a*b, x=a*c，此时我们可以知道b，c是互质的，那么就可以用欧拉来求解
/* gyt
Live up to every day */
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e6+;
const ll maxm = 1e7;
const ll mod = 1e9 + ;
const int INF = 0x3f3f3f;
const ll inf = 1e15 + ;
const db eps = 1e-;
const int kind=; ll euler(ll n){
ll res=n,a=n;
for(ll i=;i*i<=a;i++){
if(a%i==){
res=res/i*(i-);
while(a%i==) a/=i;
}
}
if(a>) res=res/a*(a-);
return res;
}
void solve() {
ll n, m; scanf("%lld%lld", &n, &m);
ll ans=;
for (ll i=; i*i<=n; i++) {
if (n%i==) {
if (i>=m) ans+=euler(n/i);
if (n/i>=m&&i*i!=n) ans+=euler(i);
}
}
cout<<ans<<endl;
}
int main() {
int t = ;
// freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &t);
while(t--)
solve();
return ;
}