区间互质计数升级

题目描述

给定正整数 n、m，统计闭区间 [1,m] 中与 n 互质的整数数量。m 很大，需要根据 n 的不同质因数使用容斥原理。

输入格式

一行输入 n、m，满足 1≤n≤10^9、1≤m≤10^12。

输出格式

输出满足 gcd(x,n)=1 的 x∈[1,m] 的数量。

样例

输入

1 1000000000000

输出

1000000000000