/*

     找规律/数位DP：我做的时候差一点做出来了，只是不知道最后的 is_one ()

                     http://www.cnblogs.com/crazyapple/p/3315436.html

     数位DP：http://blog.csdn.net/libin56842/article/details/11580497

 */

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <string>

 #include <cmath>

 using namespace std;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 int is_one(long long n)

 {

     long long m = n;

     long long i = n /  * ;

     for (; i<=m; ++i)

     {

         long long tmp = i;    int sum = ;

         while (tmp)

         {

             sum += tmp % ;

             tmp /= ;

         }

         if (sum %  == )    return ;

     }

     return ;

 }

 long long get_num(long long n)

 {

     if (n < )    return ;

     if (n <= )    return ;

     return n/ + is_one (n);

 }

 int main(void)        //HDOJ 4722 Good Numbers

 {

     //freopen ("G.in", "r", stdin);

     int t, cas = ;

     long long l, r;

     scanf ("%d", &t);

     while (t--)

     {

         scanf ("%I64d%I64d", &l, &r);

         printf ("Case #%d: %I64d\n", ++cas, get_num (r) - get_num (l-));

     }

     return ;

 }

 /*

 Case #1: 0

 Case #2: 1

 Case #3: 1

 */

 /*

     数位DP：基础题，对于一个数，把它每位数分出来，从最高位开始枚举。dp[i][(j+k)%10] += dp[i+1][j];

             dp[i][j]表示前i位数和取模是j的个数

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int MAXN = ;

 const int INF = 0x3f3f3f3f;

 ll dp[MAXN][MAXN];

 int dig[MAXN];

 ll work(ll n)   {

     ll tmp = n; int len = ;

     memset (dig, , sizeof (dig));

     while (tmp) {

         dig[++len] = tmp % ;

         tmp /= ;

     }

     memset (dp, , sizeof (dp));    int x = ;

     for (int i=len; i>=; --i)  {

         for (int j=; j<; ++j)    {

             for (int k=; k<; ++k)    {

                 dp[i][(j+k)%] += dp[i+][j];

             }

         }

         for (int j=; j<dig[i]; ++j)    dp[i][(x+j)%]++;

         x = (x + dig[i]) % ;

     }

     if (!x) dp[][]++;

     return dp[][];

 }

 int main(void)  {       //HDOJ 4722 Good Numbers

     int T, cas = ;  scanf ("%d", &T);

     while (T--) {

         ll l, r;    scanf ("%I64d%I64d", &l, &r);

         printf ("Case #%d: %I64d\n", ++cas, work (r) - work (l-));

     }

     return ;

 }

数位DP