题目传送门:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;
#define ll long long
#define re register
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define P pair<int,int>
void read(int &a)
{
a=0;
int d=1;
char ch;
while(ch=getchar(),ch>'9'||ch<'0')
if(ch=='-')
d=-1;
a=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')
a=a*10+ch-'0';
a*=d;
}
void write(int x)
{
if(x<0)
putchar(45),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
}
ll euler(ll x)
{
ll ans=x;
if(x%2==0)
{
while(x%2==0)
x/=2;
ans/=2;
}
for(re int i=3;i*i<=x;i+=2)
{
if(x%i==0)
{
while(x%i==0)
x/=i;
ans=ans/i*(i-1);
}
}
if(x>1)
ans=ans/x*(x-1);
return ans;
}
int main()
{
int T;
read(T);
while(T--)
{
ll a,b;
ll ans=0;
scanf("%lld %lld",&a,&b);
if(b==1)
{
printf("%lld
",a);
continue;
}
for(re ll i=2;i<=sqrt(a);i++)
if(a%i==0)
{
if(i>=b)
ans+=euler(a/i);
if(a/i>=b)
ans+=euler(i);
}
int x=sqrt(a+0.5);
if(x*x==a&&x>=b)///防止加两次
ans-=euler(x);
printf("%lld
",ans+1);///加上gcd(a,a)的情况,因为a>=b,所以不需要特判
}
return 0;
}