魔法数
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述


定义满足以下条件的数为"魔法数"：

* 该数是正整数
* 该数的正约数有5个

如果 a 和 b 为整数且 ，若 ，我们称 a 是 b 的一个约数。

16的正约数有1、2、4、8、16，因此16是魔法数。

20的正约数有1、2、4、5、10、20，因此20不是魔法数。

给定 l 和 r ()，求区间 中魔法数的个数。

输入描述:

第一行输入一个正整数 t，表示有 t 次询问。

接下来 t 行，每行两个整数 l 和 r，用空格隔开。



输出描述:

输出 t 行，每行一个整数，表示 l 到 r 中魔法数的个数。
示例1

输入

复制 
1
16 20

输出

复制 
1