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:

3
1 1
10 2
10000 72

Sample Output:

1
6
260

Note:

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

Info

NOJ

Provider NOJ

Code NOJ1126

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet