|
An
integer is divisible by 3 if the sum of its digits is also divisible by 3. For
example, 3702 is divisible by 3 and 12(3+7+0+2) is also divisible by 3. This
property also holds for the integer 9.
In
this problem, we will investigate this property for other integers.
Input
The first line of input is an integer T(T<100) that
indicates the number of test cases. Each case is a line containing 3 positive
integers A, B and K.
1 <= A <= B < 2^31 and
0<K<10000.
Output
For each case,
output the number of integers in the range [A, B] which is divisible by K and the sum
of its digits is also divisible by K.
|
Sample Input |
Output for Sample
Input |
|
3 1 20 1 1 20 2 1 1000 4 |
20 5 64 |
ProblemSetter: Sohel Hafiz
Special Thanks: Ivan Krasilnikov