一个正整数可以称之为快乐数,当且仅当存在一个非负整数对 (x,y),使得这个数等于 3^x \cdot 2^y。换句话说,这个数如果有质因子,只能包含 2 和 3。比如,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 |