题目描述

任何一个大于 $1$ 的正整数都能被分解为若干个质数相乘，比如 $28 = 2×2×7$ 被分解为了三个质数相乘。请问在区间 $[A, B]$ 中有多少个正整数可以被分解为 $12$ 个质数相乘？

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 $2$ 个整数 $A,B$。

输出描述

对每个输入输出一个整数表示答案。

1
2333333 23333333

25606

评测用例规模与约定：

对于所有评测用例，$1≤T≤10，1≤A≤B≤2.5×10^7$。