#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int len, C;
int nums[15], p[15], f[15][5010];

int dfs(int pos, int v, int limit) {
    if (v < 0) return 0;
    if (!pos) return 1;
    if (!limit && ~f[pos][v]) return f[pos][v];
    int up = limit ? nums[pos] : 9, res = 0;
    for (int i = 0; i <= up; i ++ ) 
        res += dfs(pos - 1, v - i * (1 << (pos - 1)), limit && i == up);
    return limit ? res : f[pos][v] = res;
}

int calc(int a, int b) {
    len = 0;
    int v = 0, k = 0;
    while (a) v += (1 << (k ++ )) * (a % 10), a /= 10;
    while (b) nums[ ++ len] = b % 10, b /= 10;
    return dfs(len, v, 1);
}

void solve() {
    int a, b; cin >> a >> b;
    cout << "Case #" << ++ C << ": " << calc(a, b) << endl;
}

int main() {
    int _; cin >> _;
    memset(f, -1, sizeof f);
    while (_ -- ) solve();
    return 0;
}