题目描述

若一个合数中所有的质因数互不相同，则把它称之为具有单纯质因数的合数。例如：\(30=2×3×5\)，它有互不相同的质因数；\(70=2×5×7\)，它也有互不相同的质因数。下面给定正整数 \(a\) 和 \(b\)，统计 \([a,b]\) 范围之内(包括 \(a\) 和 \(b\))之间具有单纯质因数的合数的个数。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；接下来每一行有两个正整数 \(a\) 和 \(b（10≤a≤b≤2×10^6）\)。

输出格式

对于每组数据，输出 \([a,b]\) 范围之内具有单纯质因数合数的个数。

样例1

输入样例1

2
10 20
10 1000000

输出样例1

3
529426

样例解释

样例 \(1\) 中，具有单纯质因数的合数是：\(10~14~15\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);