The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6. 

(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem: 

Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

Input

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

Output

For each test case,output the answer on a single line.

Sample Input

31 110 210000 72

Sample Output

16260

代码：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;long long int oula(int n){	long long int res=1;	for(int t=2;t*t<=n;t++)	{		if(n%t==0)		{			n/=t;	   		res*=t-1;		 while(n%t==0)		 {		 	n/=t;		 	res*=t;		  } 		 }		}	if(n>1)	{		res*=n-1;	}	return res;}int main(){	int n;	cin>>n;	int a,b;	long long int ans;	for(int t=0;t
        
         =b)			{				ans+=oula(a/j);			}			if(a/j>=b)			{				ans+=oula(j);			}			}		}		if(j*j==a&&j>=b)		{			ans+=oula(j);		}		cout<
         
          <