题目描述

豫让知事不成，请赵襄子解衣令刺。襄子感其忠义，脱袍相赠。豫让三跃击衣，每击皆中衣袍要害之处，大呼：”吾可报智伯于地下矣！”遂伏剑自刎。

后人感念豫让忠义，将符合以下条件的数字 $x$ 称为”忠义数”：

• 为正整数。
• 十进制表示下任意相邻两个数位不一样（象征三跃击衣，每次动作分明）。
• 十进制表示下所有数位之和为质数（象征忠义之心的纯粹）。

现给定两个整数 $l, r$($l \le r$)，请统计该区间 $l \sim r$ 内有多少个忠义数。

输入格式

第一行一个整数 $T$($1 \le T \le 100$)，表示测试数据组数。

对于每组测试数据：

一行两个整数 $l, r$($1 \le l \le r \le 10^{18}$)。

输出格式

对于每组测试数据：

输出一行一个整数，表示答案。

5
5 100
6 1000
7 10000
8 100000
9 1000000

34
274
2201
17667
147458

解释 #1

样例解释：

样例 $1$ 中 $5 \sim 100$ 中符合条件的数字有：5 7 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98，答案为 $34$。

1
100 99999999911123

5919831697926