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.
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.
For each test case, output a single line containing the required answer to the problem.
1 ≤ T≤ 10^5
1 ≤L,R ≤ 10^18
1 ≤ K≤ 50