/*
欧拉函数ψ（N）=N{∏p|N}（1－1/p）亦即:ψ(N)=（P是数N的质因数）如：
ψ（10）=10×（1－1/2）×（1－1/5）=4
ψ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8
ψ（49）=49×（1－1/7）==42
*/
#include<iostream>
#include<cmath>
using namespace std;
int euler(int n){ //欧拉函数
int ans = n;
int s = sqrt((double)n);
for(int i=2;i<=s; i++){
if(n % i == 0){
ans = ans / i * (i - 1);
while(n % i == 0)
n /= i;
}
}
if(n > 1)
ans = ans / n * (n - 1);
return ans;
}
/*
设a为大于等于m的n的一个约数，那么euler(n/a)表示的
就是所有小于a与a互质的数的个数，设任一个数为x，那
么这些数再乘以a就有gcd(n,x*a) = a;所以答案为所有n
的约数ai大于等于m的值的euler(n/ai)之和
*/
int main(){
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
if(m == 1){
cout<<n<<endl;
continue;
}
int ans = 0;
int s = sqrt((double)n);
for(int i=1; i<=s; i++){
if(n % i == 0){
if(i >= m)
ans += euler(n / i);
if(n / i >= m)
ans += euler(i);
}
}
if(n > 1 && s * s == n && s >= m)
ans -= euler(s);
cout<<ans<<endl;
}
return 0;
}