思路：
\(ans=\sum_{i \in \{x|n\%x=0\}}\phi(\frac{n}{i})\)
证明：
设\(M=it\)
\(\Rightarrow t \leq \frac{n}{i} \And (\frac{n}{i},t)=1\)
\(So\ \ t\)的可行数量为\(\phi(\frac{n}{i})\)
答案为\(ans=\sum_{i \in \{x|n\%x=0\}}\phi(\frac{n}{i})\)
\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
# define Type template<typename T>
# define read read1<int>()
Type inline T read1()
{
T t=0;
bool ty=0;
char k;
do k=getchar(),(k=='-')&&(ty=1);while('0'>k||k>'9');
do t=(t<<3)+(t<<1)+(k^'0'),k=getchar();while('0'<=k&&k<='9');
return ty?-t:t;
}
# define int long long
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int work(int n)
{
int tn=n;
for(int i=2;i*i<=n;++i)
if(!(n%i))
{
while(!(n%i))n/=i;
tn=tn/i*(i-1);
}
if(n!=1)tn=tn/n*(n-1);
return tn;
}
signed main()
{
for(int T=read;T--;)
{
int s=read,m=read,ans=0;
for(int i=1;i*i<=s;++i)
if(!(s%i))
if(i*i==s&&i>=m)ans+=work(i);
else
{
if(i>=m)ans+=work(s/i);
if(s/i>=m)ans+=work(i);
}
printf("%lld\n",ans);
}
return 0;
}