题目描述

小明最近学习了素数，素数也就是除了 1 和它本身之外没有其他因子的自然数。老师想考考他，老师会给出 q 个提问，每次提问给出两个数 x 和 y ，问在此区间内（包含 x 和 y ）有多少个数是素数。

输入格式

第一行一个整数 q

接下来共 q 行，每行两个整数，分别为 x 和 y

数据范围

对于 50% 的数据，q ≤ 100

对于 100% 的数据，q <= 10000 , 1 ≤ x , y ≤ $10^4$

输出格式

共 q 行，每行一个整数，表示问题的答案

样例

1
7 11

2