Ash was just struggling to catch rare and nicer pokemons when a mysterious guy handed him a pokemon CP map for the campus.With forces like Team Rocket on the loose,he decides its best to encrypt this list. He plans on encrypting his document using a magic number within certain limit. Magic number is a prime number whose sum and product of digits are both even. Write a program which tells Ash number of ways he can encrypt his document.

Input:

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n - m <= 100000) separated by a space.

Output:

For every test case print the total number of magic numbers p such that m <= p <= n, test cases separated by an line.