Preparing NOJ

# GCD

2000ms 65536K

## 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:

31 110 210000 72

## Sample Output:

16260

## Note:

Info

Provider NOJ

Code NOJ1126

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet