因子数小于等于4的个数
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定区间 [l,r],你需要求出 [l,r] 中因子个数小于等于 4 的正整数个数。

输入描述:


本题包含多组测试数据。

第一行给出一个整数 T \; (1 \leq T \leq 10^5),表示测试数据的组数。

接下来有 T 行,每行给出两个正整数 l,r \; (1 \leq l \leq r \leq 10^6),具体意义如题目所示。


输出描述:

输出 T 行,每行 1 个整数,其中第 i 个数表示第 i 个数据的答案。

示例1

输入

复制
1
1 6

输出

复制
6

说明

x = 6 时,它有 \{1,2,3,6 \}4 个因子。