1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: number theory
* Problem: 10533 - Digit Primes
* Accepted: 1.808
* @author Evgeni Pavlidis
*
*/

import java.io.*;
import java.util.*;

class Main {

public static final int MAX = 1000000;
private static boolean isPrime[] = new boolean[MAX+1];
private static boolean isDigitPrime[] = new boolean[MAX+1];
private static int digitPrimes[] = new int[MAX+1];

private static void sievePrimes()
{
int sum, n;
isPrime[2] = true;
for(int i = 3; i <= MAX; i+=2)
isPrime[i] = true;

int squareRoot = (int)Math.sqrt(MAX);
for(int i = 3; i <= squareRoot; i+=2)
if(isPrime[i])
for(int j = i+i; j <= MAX; j += i)
isPrime[j] = false;

isDigitPrime[2] = true;
for(int i = 3; i <= MAX; i += 2)
if(isPrime[i])
{
sum = 0;
n = i;
while( n != 0)
{
sum += n % 10;
n /= 10;
}

if(isPrime[sum])
isDigitPrime[i] = true;
}

}

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuffer output = new StringBuffer();

int low, high;
int testCases = Integer.parseInt(reader.readLine());
String[] input;

sievePrimes();

int counter = 0;
for(int i = 0; i <= MAX; i++)
{
if(isDigitPrime[i])
counter ++;

digitPrimes[i] = counter;
}

for(int c = 0; c < testCases; c++)
{
input = reader.readLine().split(" ");
low = Integer.parseInt(input[0]);
high = Integer.parseInt(input[1]);
output.append(digitPrimes[high] - digitPrimes[low-1]);
output.append("\n");

}
System.out.print(output);
}
}