#include <ctime>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 1e5 + 10;

LL a[N * 100];

LL ten[20];

LL l, r;

int cnt = 0;

int T, ca = 0;

int solve(LL x){ return upper_bound(a + 1, a + cnt + 1, x) - a - 1; }

inline int calc(LL x){

	int ret = 0;

	for (; x; x /= 10) ++ret;

	return ret;

}

LL mer(LL x, LL y){ return x * ten[calc(y)] + y; }

int main(){

	ten[0] = 1ll;

	rep(i, 1, 18) ten[i] = ten[i - 1] * 10ll;

	rep(p, 1, 1e5){

		rep(q, p + 1, 1e5){

			if (1ll * p * q >= 1e5) break;

			if (__gcd(p, q) > 1) continue;

			rep(k, 1, 1e5 / p / q){

				LL x = 1ll * k * p * p;

				LL y = 1ll * k * p * q;

				LL z = 1ll * k * q * q;

				int cnt_len = calc(x) + calc(y) + calc(z);

				if (cnt_len > 15) break;

				LL now = mer(mer(x, y), z);

				a[++cnt] = now;

				while (true){

					if (calc(z) >= 9) break;

					if (z * z % y > 0) break;

					LL nw = z * z / y;

					int nwlen = calc(nw);

					if (cnt_len + nwlen > 15) break;

					cnt_len += nwlen;

					now = mer(now, nw);

					a[++cnt] = now;

					y = z;

					z = nw;

				}

			}

		}

	}

	sort(a + 1, a + cnt + 1);

	scanf("%d", &T);

	while (T--){

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

		printf("Case #%d: %d\n", ++ca, solve(r) - solve(l - 1));

	}

	return 0;

}