题目描述

原神数 $x$ 需要同时满足以下条件：

• $x$ 为质数。

• $x$ 的十进制位两两不同。

比如 $131$ 不是原神数，因为他的百位和个位相等；$42$ 也不是，因为不是质数；$17$ 就是一个原神数。

有 $q$ 次询问，现在要你求出 $l$ 到 $r$ 之间的原神数数量。

输入格式

第一行一个正整数 $q$。

接下来 $q$ 行每行两个正整数 $l$，$r$。

输出格式

$q$ 行 $q$ 个正整数，表示答案。

4
45 66
100 140
2 90
114514 1919810

4
6
23
13321

提示

【样例解释 #1】

在 $100 \sim 140$ 之间的原神数有 $103,107,109,127,137,139$，共 $6$ 个。

数据规模与约定

本题采用捆绑测试。

• 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}$。

对于所有数据，保证 $1 \leq l \leq r \leq 10^{18}$，$1 \leq q\leq 10^5$。