最大公约数

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 gcd.in 输出文件 gcd.out

【问题描述】

两个正整数 a 和 b 的最大公约数 GCD(a,b) ，有时记为（ a,b ），是对于 a 、 b 来说最大的共同约数，举例来说，（ 1 ， 2 ） =1 ，（ 12 ， 18 ） =6 。
利用欧几里得算法很容易求出（ a,b ），现在 Carp 正在思考一个更复杂的问题：
给定整数 N 和 M ，到底存在多少个 X ，使得其满足条件： 1 ≤ X ≤ N 并且 (X,N) ≥ M 。

 
【输入格式】
输入文件第一行有一个整数 T （ T ≤ 3000 ），表示测试数据的个数，接下来有 T 行，每行包含两个数 N 和 M ， 1 ≤ N ≤ 1000000000 ， 0 ≤ M ≤ 1000000000 ，表示一组测试数据。
【输出格式】
对于每组测试数据，输出一个结果，每个结果占一行。
【输入样例】
gcd.in
3
1 1
10 2
10000 72
gcd.out
1
6
260