### 问题描述 森林中住着一群小狐狸，他们生活在一条直线上。一些小狐狸的房子的位置是被其他小狐狸羡慕的，他们的位置坐标 $x$ 通常有这样的特征：$x$ 是一个质数，并且 $x$ 可以被表示为 $x=a^2+b^2$ ( $a$ 和 $b$ 是任意的正整数）。位置坐标不满足这个条件的房子是没有狐狸羡慕的，住在这里的狐狸被称作是伤心的狐狸。现在把问题简化为坐标轴上所有位置都有狐狸，请你求出给定区间有多少个伤心的狐狸。 ### 输入格式 输入的第一行是一个数字 $t$ ,表示有 $t$ 次询问。 接下来输入 $t$ 行数字，每行包括一个 $l$ 和一个 $r$ ，表示查询的区间（注意题目中区间描述为闭区间）。 测试数据中保证 $1 \leq t \leq 1000 ， 1 \leq l \leq r \leq 10^8$ 。 ### 输出格式 对于每一次询问，输出一个数字，表示询问区间中伤心的狐狸的数量。 ### 样例输入 ``` 2 3 5 5 10 ``` ### 样例输出 ``` 2 5 ``` ### 说明 $3$ 到 $10$ 中被羡慕的位置只有 $5$ ，其他位置上的狐狸均是伤心的。