/*

题意：给出N，M让你求出 X的个数 ，X满足GCD(X,N)>=M;

初步思路：首先N的比M大的因子肯定是，是这个因子的倍数的也是。除此之外就没了，因为其他的数GCD(other,N)=1,如果M等于1的话，直接输出N就行了

    现在的问题就是怎么找因子的倍数，因为会有重复的，res=N/x(x是N的因子);对于因子x有res个可满足的结果，但是在计算过程中会有重复的存在，

    这样，令pi<=res && GCD(pi,res)==1,这样保证了 pi*x不会重复，就转化成了，求N/x的欧拉函数

*/

#include<bits/stdc++.h>

using namespace std;

/**************************欧拉函数模板*****************************/

//直接求解欧拉函数

int euler(int n){ //返回euler(n)

    int res=n,a=n;

    for(int 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;

}

/**************************欧拉函数模板*****************************/

int solve(int n,int m){

    if(m==) return n;

    int cur=;

    for(int i=;i*i<=n;i++){

        if(n%i==){//i是n的因子

            if(i>=m){

                cur+=euler(n/i);

            }

            if(i*i!=n){//对面的因子

                if(n/i>=m){

                    cur+=euler(n/(n/i));

                }

            }

        }

    }

    return cur+;

}

int t;

int n,m;

int main(){

    //freopen("in.txt","r",stdin);

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        printf("%d\n",solve(n,m));

    }

    return ;

}