题目描述

小新最近参加了区里举办的数学奥数竞赛，有这么一道题难住了他。素数（又称质数），是指其除了能整除1和自身外，都不能整除任何数的自然数，同时规定1不是素数。针对 $q$ 次提问，每次给定两个正整数 $x$ 和 $y$，规定 $x<y$ ，求从 $x$ 到 $y$ 范围内（包含 $x$ 和 $y$）的素数个数。

输入格式

第一行，一个正整数$q$，表示提问次数。

后面 $q$ 行，每行两个正整数$x$ 和 $y$

输出格式

$q$ 行，每行一个整数，表示从 $x$ 到 $y$ 范围内（包含 $x$ 和 $y$）的素数个数。

样例输入

2
2 10
9 15

样例输出

4
2

样例说明

对于第一次询问，有{2, 3, 5, 7}这4个素数；对于第二次询问，有{11, 13}这两个素数。

数据范围

对于20%的数据，$1 \leq q \leq 10, 1 \leq x<y\leq 10^3$

对于50%的数据，$1 \leq q \leq 10^3, 1 \leq x<y\leq 10^5$

对于100%的数据，$1 \leq q \leq 10^5, 1 \leq x<y\leq 10^5$