题目背景

质数（素数）作为数论的基石，具有深远的意义和广泛的应用。

题目描述

给定 $l,r$，求区间$[l,r]$ 内质数的个数。

输入

第一行有一个整数，分别代表询问次数$n( 1 \leq n \leq 2\times10^6 )$。

接下来 n 行，每行两个整数 $l,r( 1 \leq l\leq r\leq1\times10^4 )$，代表一次查询。

输出

对于每次查询输出一行一个整数，为区间质数个数。

样例说明

输入 #1

2
1 6
5 8

输出 #1

3
2

限制条件

1s, 512miB 每次测试。