### 问题描述 小明最近新学了一个概念，叫做多重质数。它的定义是这样的：对于一个正整数 $n$，$n$ 是质数，并且 $\lfloor\frac{n}{2}\rfloor$ 也是质数，那么就称这个正整数 $n$ 为多重质数，其中 $\lfloor \frac{n}{2} \rfloor$ 表示不超过 $\frac{n}{2}$ 的最大正整数。小明现在想知道，对于给定的区间 $[l,r]$，其中有多少个多重质数。一共有 $q$ 次问询，每次问询输出一个答案。 ### 输入格式 第一行输入一个整数 $q$，表示问询的次数。 接下来 $q$ 行，每行包括两个数 $l$，$r$。表示要查询的区间的左右端点。 数据保证 $1\le q \le 10^5$，$1 \le l, r\le 10^5$。 ### 样例输入 ```text 3 1145 1918 6081 71905 5781 21790 ``` ### 样例输出 ```text 11 425 127 ```