令 $$$f$$$($$$x$$$) 为 $$$x$$$ 的二进制对数的下限。换句话说,$$$f$$$($$$x$$$)是最大的非负整数$$$y$$$,使得$$$2^y$$$不超过$$$x$$$。
设 $$$g$$$($$$x$$$) 为 $$$x$$$ 以 $$$f$$$($$$x$$$) 为底的对数下限。换句话说,$$$g$$$($$$x$$$)是最大的非负整数$$$z$$$,使得$$${f(x)}^{z}$$$不超过$$$x$$$。
您收到 $$$q$$$ 查询。第 $$$i$$$ 查询由两个整数 $$$l_i$$$ 和 $$$r_i$$$ 组成。查询的答案是所有整数 $$$k$$$ 的 $$$g$$$($$$k$$$) 之和,使得 $$$l_i \leq k \leq r_i$$$。由于答案可能很大,请以 $$${10^9 + 7}$$$ 为模打印它们。
输入
第一行包含一个整数 $$$q$$$ — 查询数量 ($$$1 \leq q \leq 10^5$$$)。
接下来的 $$$q$$$ 行每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ — 第 $$$i$$$ 查询的边界 ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$)。
输出
对于每个查询,输出查询模 $$$10^9 + 7$$$ 的答案。
示例
输入 #1
12 4 6 4 7 4 8 4 100000 179 1000000000000000000 57 179 4 201018959 7 201018960 729 50624 728 50624 728 50625 729 50625
输出 #1
6 8 9 348641 41949982 246 1 0 149688 149690 149694 149692
注意
下表包含所有 $$$x$$$ 的函数 $$$f$$$($$$x$$$) 和 $$$g$$$($$$x$$$) 的值,使得 $$$1 \leq x \leq 8$$$。
$$$x$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$f$$$$$$0$$$$$$1$$$$$$1$$$$$$ 2$$$$$$2$$$$$$2$$$$$$2$$$$$$3$$$$$$g$$$$$$-$$$$$$-$$$$$$-$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$1$$$