题目描述

在数字王国里，国王最喜欢两种神奇的数字：

第一种是回文数：它从左往右读和从右往左读都一样，比如 $11、131、2442$。

第二种是质数：它只能被 $1$ 和它自己整除，比如 $2、3、5、7、11$。

如果一个数字既是回文数又是质数，例如 $11、131$，国王就把它叫做 “回文宝石数”，并把它收藏进皇家宝库。

有一天，王国的史官接到了 $n$ 条命令，每条命令给出两个整数 $a$ 和 $b$，要求史官统计出 $a \sim b$ 范围内一共有多少个回文宝石数。

史官一个人忙不过来，他想请你帮忙写一个程序，快速告诉他每一条命令的答案。

输入格式

第一行输入一个整数 $n\ (1 \leq n \leq 10^5)$

接下来 $n$ 行，每行 $2$ 个整数 $a, b\ (1 \leq a, b \leq 10^7)$.

输出格式

输出 $n$ 行，每行一个整数，代表 $a \sim b$ 范围内一共有多少个回文宝石数。

样例

2
1 10
500 1000

4
6