如果一个整数 $x$ 的十进制表示可以通过从整数 $y$ 的十进制表示中删除若干位（可以不删除，但不能全部删除）得到，则称 $x$ 是 $y$ 的十进制子序列。

如果一个整数 $x \ge 2$ 且其仅有的正整数约数为 $1$ 和 $x$，则称 $x$ 为质数。

如果不存在整数 $y$ 使得 $y$ 是 $x$ 的十进制子序列且 $y$ 是质数，则称 $x$ 为次级整数。例如，$168$ 是次级整数，因为 $1, 6, 8, 16, 18, 68, 168$ 均不是质数；而 $169$ 不是次级整数，因为 $19$ 是质数。

求给定区间 $[l, r]$ 中次级整数的个数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10$)，表示区间个数。

接下来 $n$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le 10^{18}$)，表示区间的边界。

输出格式

按输入顺序，输出每个给定区间中次级整数的个数。

样例

输入格式 1

3
8 16
157 174
42 239

输出格式 1

5
4
36

说明

在样例测试用例中，属于 $[8, 16]$ 的次级整数有 $8, 9, 10, 14, 16$，属于 $[157, 174]$ 的次级整数有 $160, 164, 166, 168$。