Sumit, a bright student with a passion for problem-solving, recently encountered a challenging question.

The task was to count the numbers within a range, specifically between \(L\) and \(R\), where the product of their individual digits is divisible by a positive integer \(P\).

Sumit loves challenges and turned to you, his helpful roommate, for assistance. Can you assist Sumit in solving this problem and showcase his impressive problem-solving skills?

Input Format:

The first line contains an integer \(T\), representing the number of test cases.

Each of the following \(T\) lines contains three integers: \(L\), \(R\), and \(P\).

Output Format:

For each test case, print the number of integers that meet the condition in a separate line.

Constraints:

\(1 \leq T \leq 10 \\ 1 \leq L \leq R \leq 10^9 \\ 1 \leq P \leq 10^9\)