An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12 (3+7+0+2) is also divisible by 3. This property also holds for the integer 9.

In this problem, we will investigate this property for other integers.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains three positive integers A, B and K (1 ≤ A ≤ B < 2³¹ and 0 < K < 10000).

Output

For each case, output the case number and the number of integers in the range [A, B] which are divisible by K and the sum of its digits is also divisible by K.

Sample Input

Output for Sample Input

3

1 20 1

1 20 2

1 1000 4

Case 1: 20

Case 2: 5

Case 3: 64

數組開dp[12][10010][90] 就會爆內存

考慮到只要K>=90 就不用DP了(個位數之和不會超過90)

因此只要將數組開到dp[12][90][90]

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll dp[12][90][90];
vector digit;
ll m,n,k;
ll dfs(int pos,int mod,int sum,int done){
    if(pos==-1) return sum==0&&mod==0;
    if(!done && ~dp[pos][mod][sum]) return dp[pos][mod][sum];
    ll res = 0;
    int end = done?digit[pos]:9;
    for(int i = 0; i <= end; i++){
        res += dfs(pos-1,(mod*10+i)%k,(sum+i)%k,done&&i==end);
    }
    if(!done) dp[pos][mod][sum] = res;
    return res;
}
ll solve(ll x){
    digit.clear();
    while(x){
        digit.push_back(x%10);
        x /= 10;
    }
    return dfs(digit.size()-1,0,0,1);
}
int main(){
    int ncase,T=1;
    cin >> ncase;

    while(ncase--){
       cin >> m >> n >> k;
       if(k >= 90){
            printf("Case %d: 0\n",T++);
            continue;
       }
       memset(dp,-1,sizeof dp);
       printf("Case %d: %d\n",T++,solve(n)-solve(m-1));
    }
    return 0;
}