几乎是素数 Almost Prime Numbers

题意翻译

输入两个正整数$L,U(L\leq U<10^{12})$,统计区间$[ L,U ]$的整数中有几个满足：它本身不是素数，但只有一个素因子。例如，$4$、$27$都满足条件。 Translated by @HNFMS_tomoo @Planet6174

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1480 [PDF](https://uva.onlinejudge.org/external/105/p10539.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10539/57056b78510d3231145c5d829f0bf70ad9bc84b6.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10539/57a619b6b278b0e8ab270622f3532575eb389c37.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10539/54c6334de1dccc8d6de0834ca1e3163626ea0dc5.png)

输入输出样例

输入样例 #1

3
1 10
1 20
1 5

输出样例 #1

3
4
1