Distinct Prime Digits

An Original Genshin number is a prime number whose decimal digits are pairwise distinct. For example, 131 is not an Original Genshin number because the hundreds and ones digits are the same; 42 is not because it is not prime; while 17 is an Original Genshin number.

You are given q queries. In each query, you are provided with two integers l and r. Your task is to determine the number of Original Genshin numbers in the interval [l, r].

Note: A one‐digit prime is considered to have distinct digits by default.

inputFormat

The first line contains a single integer q (q ≥ 1) — the number of queries.

Each of the next q lines contains two space-separated integers l and r (1 ≤ l ≤ r) representing the range to be queried.

outputFormat

For each query, output a single integer representing the number of Original Genshin numbers in the interval [l, r].

sample

3
1 30
30 100
1 100

9
15
24