Good Numbers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 428 Accepted Submission(s): 149

Problem Description

If we sum up every digit of a number and the result can be exactly divided by 10, we say this number is a good number.

You are required to count the number of good numbers in the range from A to B, inclusive.

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.

Each test case comes with a single line with two numbers A and B (0 <= A <= B <= 10

¹⁸).

Output

For test case X, output "Case #X: " first, then output the number of good numbers in a single line.

Sample Input

      2 1 10 1 20 

Sample Output

      Case #1: 0 Case #2: 1 
Hint
 The answer maybe very large, we recommend you to use long long instead of int. 

Source

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define INF 99999999using namespace std;const int MAX=22;__int64 dp[MAX][10];//分别代表长度为i位数和mod 10为j的个数 int digit[MAX];void digit_dp(){//计算每长度为i为的数mod 10 == 0的个数 dp[0][0]=1; for(int i=1;i
             
              =1;--i){ for(int j=0;j