题目描述

素数（质数）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。定义双重素数为这样的素数：它的各位数字之和也是一个素数。给定一个闭区间，试确定在该区间内双重素数的个数。

输入格式

输入包含多组测试数据。 输入第一行包含一个整数 T，表示测试数据的组数。接下来每行一组测试数据，每组测试数据包含以空格分隔的两个整数 L 和 R。

输出格式

每组测试数据输出一行，包含一个整数，表示在闭区间 [L, R] 内双重素数的个数。

输入输出样例

4
3 3
4 4
1 5
1 15

1
0
3
5

提示

样例说明

从 1 到 15 共有 6 个素数：2，3，5，7，11，13。前五个素数各自的数字之和也是素数，因此都是双重素数。素数 13 的各位数字之和为 4，不是素数，故 13 不是双重素数。

数据范围

对于 100% 的数据，$1≤T≤100,1 \leq L \leq R \leq 1 \times 10 ^ 7$