I think it can be done with dynamic programming (to be able to count f (x) = the number of numbers up to x with the desired property, so the answer is f (R) — f (L-1)). The state is how many digits you've placed, whether or not you have already gone below x on some digit, and the current sum of cubes of digits mod m. Then you try each possible digit and get a new state for each valid digit.

Calculate F(l, m, r) as number of numbers with length not more than l, such that sum of the cubes of their digits equals to r by modulo m. Then each query can be processed by O(sum_of_digits).

Lets d_i be the i-th digit of query number n and l its length. Iterate by prefixes, for each d < d_i adding to answer F(l - i - 1, m,  - (sum_of_cubes_on_prefix_i - 1 + d_i³)%m).