UOJ Logo LFYZ Online Judge

LFYZOJ

#51. 【模板】素数筛(【2018年2月期末欢乐赛】虚伪的数)

统计

问题描述

一天,poorpool 在写数学作业。

他写导数累了,就开始研究数。

俗话说,对于一个大于 1 的整数 $n$,它总能写成一堆大于 1 的整数的积。poorpool 觉得那些可以写成好多个(多于 1 个)大于 1 的整数的积的整数太虚伪了,于是他就问你 $m$ 个问题,每个问题给出你 $i,j$,问你在 $[i,j]$ 之间不虚伪的数有几个。

输入格式

第一行一个整数 $m$,是 poorpool 问你的问题的个数。

下来 $m$ 行,每行两个整数 $i,j$。

输出格式

输出 $m$ 行。

对于每个询问,请你输出在 $[i,j]$ 之间不虚伪的数有几个并换行。

样例一

input

2
3 10
5 7

output

3
2

数据范围与约定

对于 $40\%$ 的数据,$2 \leq i \leq j \leq 100$,$m \leq 10$。

对于 $100\%$ 的数据,$2 \leq i \leq j \leq 5000000$,$m \leq 500000$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$