## Description:

The greatest common divisor GCD(a,b) of two positive integer a and b,sometimes written (a,b),

is the largest divisior 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 difficlut problem.

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

≥M.

## Input:

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

## Output:

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

## Sample Input:

3

1 1

10 2

10000 72

## Sample Output:

1

6

260

## Note:

本题由旧版NOJ导入，来源：第九届中山大学程序设计竞赛预选题