Magical Numbers

You are given several test cases. In each test case, you are provided three integers l, r, and d.

A magical number is defined as a number in the interval \([l, r]\) whose digit sum is divisible by d. The digit sum of a number is the sum of all its digits. For example, the digit sum of 123 is \(1+2+3=6\).

Your task is to count the number of magical numbers in the given range. If there are no magical numbers in the range, return \(-1\).

Example:

• For \(l=1, r=10, d=3\): the answer is 3.
• For \(l=11, r=20, d=5\): the answer is 2.
• For \(l=1, r=5, d=9\): the answer is -1.
• For \(l=100, r=200, d=11\): the answer is 9.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each of the following \(T\) lines contains three space-separated integers: \(l\), \(r\), and \(d\).

outputFormat

For each test case, output one integer on a new line representing the count of magical numbers in the range \([l, r]\). If none exist, output \(-1\).

## sample

4
1 10 3
11 20 5
1 5 9
100 200 11

3
2
-1
9

</p>