package interviewstreet;

import java.util.Scanner;

public class lucky_num {

	public static void main(String[] args) {

		lucky_num sr = new lucky_num();
		Scanner scanner = new Scanner(System.in);
		int no_cases = scanner.nextInt();
		for (int i = 0; i < no_cases; i++) {
			System.out.println(sr.solve(scanner.nextLong(), scanner.nextLong()));
		}
	}

	private int solve(long l, long m) {
		int count = 0;
		for (long i = l; i <= m; i++) {
			if (logic(i)) {
				count++;
			}
		}
		return count;
	}

	private boolean logic(long i) {
		return (isSUM(i) && isSUMsq(i));
	}

	private boolean isSUMsq(long i) {
		int sum = 0;
		while (i > 9) {
			long k = i % 10;
			i = i / 10;
			sum += k * k;
		}
		sum += i * i;
		return (isPrime(sum));
	}

	private boolean isSUM(long i) {
		int sum = 0;
		while (i > 9) {
			long k = i % 10;
			i = i / 10;
			sum += k;
		}
		sum += i;
		return (isPrime(sum));
	}

	private boolean isPrime(int num) {
		if(num==2)
			return true;
		// check if n is a multiple of 2
		if (num % 2 == 0 || num==1 )
			return false;
		// if not, then just check the odds
		for (int i = 3; i * i <= num; i += 2) {
			if (num % i == 0)
				return false;
		}
		return true;
	}
}