Squares and Cubes

Translated from ROI 2018 Regional. Day1 T2. In this problem, mathematicians study the relationship between the distribution of squares of natural numbers and cubes of natural numbers.

Given non-negative integers \(a\), \(b\), and \(k\). Consider the set \(S = \{a, a+1, \ldots, b\}\). We define the \(k\)-density of \(S\) as the number of elements in the set \[ T = \{ (x,y) \mid x \in \mathbb{N},\; y \in \mathbb{N},\; x^2 \in S,\; y^3 \in S,\; |x^2 - y^3| \le k \} \] Your task is to compute the \(k\)-density of \(S\).

Note: Here \(\mathbb{N}\) denotes the set of non-negative integers.

inputFormat

The input consists of three non-negative integers \(a\), \(b\), and \(k\) separated by spaces.

It is guaranteed that \(0 \le a \le b\) and \(k \ge 0\).

outputFormat

Output a single integer representing the \(k\)-density of the set \(S = \{a, a+1, \ldots, b\}\).

sample

0 100 0

3