记录编号	335067	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	派特三石	是否通过	通过
代码语言	C++	运行时间	0.567 s
提交时间	2016-11-01 20:52:37	内存使用	0.31 MiB

/*
	Name: 最大公约数 
	Date: 01/11/16 20:47
	Description: 对于n的约数d，d和d的倍数x,gcd(x,n)==d,如果d大于等于m，则x都符合要求。
	x的个数为phi(n/i) 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;
int n,m,ans;
inline void read(int &x)
{
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
}
inline void write(int &num){
	int cnt=0;char str[21];
	while(str[++cnt]=num%10+48,num/=10);
	while(putchar(str[cnt]),--cnt);
}
inline int phi(int x){
	int dd=x;
	for(int i=2;i*i<=x;i++){
	    if(x%i==0){
			dd=dd/i*(i-1);
			while(x%i==0)x/=i;
	    }
	}
	if(x>1)dd=dd/x*(x-1);
	return dd;
}
inline void init()
{
	ans=0;
	read(n);read(m);
	if(m==1)
	{
		write(n);
		return;
	}
	for(int i=1;i*i<=n;++i)
	{
		if(n%i==0)
		{
			if(i>=m)
			ans+=phi(n/i);
			if(n/i!=i&&(n/i>=m))
			ans+=phi(i);
		}
	}
	write(ans); printf("\n");
}																																									
int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	int T;
	read(T);
	while(T--)init();getchar();getchar();
	//printf("%.2lf\n",(double)clock()/CLOCKS_PER_SEC);
}