Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

m-Beautiful Numbers

By moshiur_cse15 · Limits 3s, 512 MB

m-Beautiful Numbers is a number which is divisible by m and the sum of the digits is also divisible by m. For example, 268 is a 4-Beautiful Number, but 68 and 26 are not 4-Beautiful Number.

In this problem, you’ll be given 3 integers, L, R, and m, you’ve to tell the number of m-Beautiful Numbers in between L and R inclusive . As the answer can be very large, you have to print it modulo 109+7.

Input

The first line of the input will contain a number T, number of test cases to follow. Next T lines will contain 3 integers L, R, and m each as stated in description.
1 ≤ T ≤ 105
1 ≤ L ≤ R ≤ 1050
1 ≤ m ≤ 50

Output

For each case, you have to print the number of m-Beautiful Numbers in between L and R inclusive modulo 109+7.

Sample

InputOutput
2
1 20 3
1 20 4
6
2

3-Beautiful numbers between 1 to 20: 3, 6, 9, 12, 15, and 18.
4-Beautiful numbers between 1 to 20: 4, and 8.



Discussion
Statistics

33% Solution Ratio

dip_BRUREarliest, 4w ago

EgorKulikovFastest, 0.9s

dip_BRURLightest, 18 MB

mahdi.hasnatShortest, 1654B

Submit

Login to submit