Problem Description

A Genshin number $x$ must satisfy both of the following conditions:

• $x$ is a prime number.
• All decimal digits of $x$ are pairwise distinct.

For example, $131$ is not a Genshin number because its hundreds digit equals its ones digit; $42$ is not because it is not prime; $17$ is a Genshin number.

There are $q$ queries. You need to find the number of Genshin numbers between $l$ and $r$ (inclusive).

Input Format

The first line contains a positive integer $q$.

The next $q$ lines each contain two positive integers $l$ and $r$.

Output Format

Output $q$ lines. Each line contains one positive integer, which is the answer to the corresponding query.

4
45 66
100 140
2 90
114514 1919810

4
6
23
13321

Hint

Sample Explanation #1

Between $100$ and $140$, the Genshin numbers are $103,107,109,127,137,139$, a total of $6$.

Constraints and Notes

This problem uses bundled tests.

• Subtask 0 (15 pts): $1 \le l \le r \le 10^2$.
• Subtask 1 (15 pts): $1 \le l \le r \le 10^4$.
• Subtask 2 (35 pts): $1 \le l \le r \le 10^7$.
• Subtask 3 (35 pts): $1 \le l \le r \le 10^{18}$.

For all testdata, it is guaranteed that $1 \leq l \leq r \leq 10^{18}$ and $1 \leq q \leq 10^5$.

Translated by ChatGPT 5