#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){ return (b==0) ? a : gcd(b, a % b); }
int main()
{
    int T;scanf("%d", &T);
    while(T--)
    {
        int n, m;scanf("%d%d", &n, &m);
        int ans=0;
        for(int i=1;i<=n;i++)
            if(gcd(n, i)>=m)
                ans++;
        printf("%d\n", ans);
    }
    return 0;
}