In the ancient Kingdom of Arithmethia, the Royal Astronomers have discovered a peculiar cosmic alignment. The stars are arranged in a single line, each possessing a numerical energy value. The Grand Wizard believes that true cosmic harmony is only achieved by celestial bodies that exhibit a rare dual property known as the "PADS" (Parity-Alternating Divisible Sum) state.
A positive integer is considered to be in the "PADS" state if it satisfies two strict laws of nature:
The Law of Opposition: The energy of the digits must fluctuate perfectly. Every digit must have a different parity (odd/even status) from its immediate neighbors. For example, if a digit is Odd, its neighbors must be Even, and vice versa.
The Law of Unity: The sum of all digits in the number must be perfectly divisible by a sacred cosmic constant K.
The King wants to know how many integers between range L and R (inclusive) satisfy these conditions so he can predict the next era of prosperity.
Your task is to write a program that counts the number of such integers.
The first line contains a single integer T, the number of test cases.
Each test case consists of a single line containing three space-separated integers:
L: The lower bound of the range.
R: The upper bound of the range.
K: The sacred divisor.
For each test case, output a single integer: the count of numbers in [L, R] that satisfy both the Law of Opposition and the Law of Unity.
1 ≤ T ≤ 100
1 ≤ L ≤ R ≤ 1018
1 ≤ K ≤ 100
| Example Input | Example Output |
|---|---|
3 1 20 3 10 50 5 100 500 7 |
2 4 9 |