求出区间 [l,r][l,r][l,r] 中与 nnn 互质的数的个数。
输入
三个整数 l,r,n (1≤l≤r≤109,1≤n≤109)l,r,n \ (1 \leq l \leq r \leq 10^9, 1 \leq n \leq 10^9)l,r,n (1≤l≤r≤109,1≤n≤109)。
输出
一个整数,表示答案。
样例
1 10 2
5
3 15 5
10