5480: X-liked Counting
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
David is alway fond of new kinds of numbers.
He defines a number x−liked if any of its prefixes or suffixes can be divided by x. A prefix is a contiguous part which begins at the leftmost position of the number and ends at any position of the number, and a suffix is a contiguous part which begins at any position of the number and ends at the rightmost position of the number. For example, 12 is a prefix of 123 while 23 is a suffix of it. The number itself can be a prefix or a suffix of itself.
Now David wants to know how many x−liked integers there are in the range [l,r]. However, since David doesn't like the number 7, he won't allow digit 7 to occur in the numbers, so you don't need to count in numbers like 27,372,774 etc. because they all have at least one digit equals to 7. Please tell him how many x−liked integers there are in the range [l,r] with no digit equals to 7.
He defines a number x−liked if any of its prefixes or suffixes can be divided by x. A prefix is a contiguous part which begins at the leftmost position of the number and ends at any position of the number, and a suffix is a contiguous part which begins at any position of the number and ends at the rightmost position of the number. For example, 12 is a prefix of 123 while 23 is a suffix of it. The number itself can be a prefix or a suffix of itself.
Now David wants to know how many x−liked integers there are in the range [l,r]. However, since David doesn't like the number 7, he won't allow digit 7 to occur in the numbers, so you don't need to count in numbers like 27,372,774 etc. because they all have at least one digit equals to 7. Please tell him how many x−liked integers there are in the range [l,r] with no digit equals to 7.
输入
The first line contains one integer T(1≤T≤10) , the number of testcases.
For each testcase, there is one line which contains three non-negative integers, l,r and x.
1≤l≤r≤1018
1≤x≤500
For each testcase, there is one line which contains three non-negative integers, l,r and x.
1≤l≤r≤1018
1≤x≤500
输出
For each testcase, output one number in one line, how many x−liked integers there are in the range [l,r] with no digit equals to 7.
样例输入 复制
1
11 20 4
样例输出 复制
5提示
In the sample, there are five valid integers, 12(12 can be divided by 4), 14(4 can be divided by 4), 16(16 can be divided by 4), 18(8 can be divided by 4), 20(20 and 0 both can be divided by 4).