题目描述

小瑶酷爱数学，这两天在研究完全立方数（一个数如果是另一个整数的完全立方，那么我们就称这个数为完全立方数，如8=2 * 2 * 2，64=4 * 4 * 4）。想通过编程解决给定范围[a, b]内有多少个不含有指定因子x的完全立方数。

输入格式

一行三个数a, b, x。

输出格式

一行一个数，表示满足要求的完全立方数的个数。

样例

3 12 4

0

解释#1

3~12之间有一个完全立方数8=2^3，但4是8的因子，所以输出的应该是0。

11 123 5

2

解释#1

11~123之间有两个完全立方数27=3^3,64=4^3，5都不是27和64的因子，所以输出的应该是2。

数据范围

对于30%的数据，1≤a≤b≤1000，1≤x≤100

对于50%的数据，1≤a≤b≤10^9，1≤x≤10^4

对于100%的数据，1≤a≤b≤10^18，1≤x≤10^9。