题目描述

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

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

• 为正整数。
• 十进制表示下任意相邻两个数位不一样。
• 十进制表示下所有数位之和为质数。

现给定两个整数 $l,r(l \le r)$，请统计满足 $l \le x \le 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
100 999999999911123

5919831697926