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 < 231 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 3 1 20 1 1 20 2 1 1000 4 Sample Output 20 5 64