#include <bits/stdc++.h>

using namespace std;

const int N = 6e6 + 7;

int q, b[N], cnt, c[N], cnt1;

bool vis[1000000007];

vector<long long> st; 

bool pd(long long x) {
	int a[17];
	for (int i = 0; i <= 9; i++) a[i] = 0;
	while (x) {
		a[x % 10]++;
		if (a[x % 10] > 1) return 0;
		x /= 10;
	}
	return 1;
}

int main() {
	clock_t t = clock();
	vis[1] = 1;
	for (int i = 2; i <= 100000000; i++) {
		if (!vis[i]) b[++cnt] = i;
		for (int j = 1; j <= cnt && i * b[j] <= 100000000; j++) {
			vis[i * b[j]] = 1;
			if (i % b[j] == 0) break;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		if (pd(b[i])) c[++cnt1] = b[i];
	}
	for (int i = 1; i <= cnt1; i++) st.insert(upper_bound(st.begin(), st.end(), c[i]), c[i]);
	scanf ("%lld", &q);
	while (q--) {
		long long l, r;
		scanf ("%lld%lld", &l, &r);
		printf ("%lld\n", upper_bound(st.begin(), st.end(), r) - lower_bound(st.begin(), st.end(), l));
	}
	cerr << "TIME: " << 1000 * (clock() - t) / CLOCKS_PER_SEC << "ms" << endl;
	return 0;
}