### 问题描述 如果一个数 $x$ 是素数，且 $\lfloor\dfrac{x}{2}\rfloor$ 也是素数，则称 $x$ 是好数，例如 $5,7,11$ 都是好数。 现在给定你一个正整数 $n$，有 $q$ 组查询，每组查询给出一个区间 $[l,r]$，$1\le l \le r \le n$，询问该区间内有多少个好数。 素数：如果一个数的约数只有 $1$ 和本身，则为素数。 ### 输入格式 第一行二个整数 $n,q$，表示区间上界和查询数。 接下来 $q$ 行，每行一对 $[l,r]$ 表示查询的区间。 ### 输出格式 对于每次查询，输出区间好数的数量。 ### 样例输入 ```text 20 3 1 9 7 20 11 17 ``` ### 样例输出 ```text 2 2 1 ``` ### 说明 $5,7,11$ 是好数，原因如下： 1. $5,2$ 是素数，所以 $5$ 是好数。 2. $7,3$ 是素数，所以 $7$ 是好数。 3. $11,5$ 是素数，所以 $11$ 是好数。 ### 评测数据规模 $1\le n\le 10^6,1\le q\le 10^5,1\le l\le r\le n$。