Galaxy and His coder gf

0

0 votes
Medium-Hard
Problem

Galaxy, a great programmer of NIT-Agartala is busy in upcoming new year celebration. Yesterday his GF got stuck on a programming problem. But galaxy is busy so help her to solve the problem as you are also a good programmer.

The problem statement is as follows:

Given two number L and R, count all number between L and R inclusively whose sum of the cube of digits is divisible by K.

Input:

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first and only line of each test case contain 3 space separated integers L, R and K.

Output:

For each test case, output a single line containing the required answer to the problem.

Constraints:

1 ≤ T≤ 10^5

1 ≤L,R ≤ 10^18

1 ≤ K≤ 50

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?