1233. 快乐数

一个正整数可以称之为快乐数,当且仅当存在一个非负整数对 (x,y),使得这个数等于 3^x \cdot 2^y。换句话说,这个数如果有质因子,只能包含 23。比如,1,2,3,4,6,9,18,36 是快乐数,而 7,10,11,15,31 不是快乐数,而给定两个正整数 l,r,请问区间 [l,r] 中有多少个快乐数?

输入

输入包含多组测试用例(保证测试用例数量 1 \leq T \leq 100),以 EOF 作为结束标志。

每组数据占一行,每行包含两个正整数 l,r \ (1 \leq l \leq r \leq 2 \cdot 10^{17})

输出

对于每组数据,每行输出一个正整数,表示答案。

样例

标准输入 复制文本
2 500
1 7
100 200000000000
标准输出 复制文本
32
5
456
登录以提交代码。
单点时限 3 秒
内存限制 128 MB
提交 259
通过 140