题目描述

给定整数区间 $[a,b]$。

求有多少个不同的无序整数对 $(x,y)$ 满足：

• $x,y\in[a,b]$；
• $x\mathbin{|}y=x+y$，其中 $|$ 表示按位或（bitwise OR）。

只交换两个数次序得到的两个数对视为同一个数对。

输入格式

第一行包含测试数据组数 $Z$：

$1\le Z\le1000$。

接下来 $Z$ 行，每行包含两个整数 $a,b$：

$1\le a<b\le10^{18}$。

输出格式

对于每组数据，输出满足条件的无序数对数量对 $10^9+7$ 取模后的结果。

样例

2
1 8
8 20

13
22

样例说明

第一组数据中的 $13$ 个数对为：

$(1,2),(1,4),(1,6),(1,8),(2,4),(2,5),(2,8),(3,4),(3,8),(4,8),(5,8),(6,8),(7,8)$。

例如 $6\mathbin{|}8=14=6+8$。

子任务