当N遇上M

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

两个整数a,b互质定义为gcd(a,b) = 1,现在给出两个整数n(1 <= n <= 10^15)和 m(1 <= m <= 10^9),求出[1,n]内与m互质的数的个数。

Input

 多组输入,每行一组,有两个整数n,m。

Output

 对每一组输入输出一行,表示[1,n]内有多少个数与m互质。

Sample Input

10 2
10 1
15 5
10000000 7

Sample Output

5
10 
12
8571429

Hint

 

Source

第六届山东理工ACM网络编程擂台赛决赛