P10404 "XSOI-R1" Genshin Numbers

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).

The first line contains a positive integer $q$. The next $q$ lines each contain two positive integers $l$ and $r$.

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

**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