给定两个非负整数 $X$ 和 $Y$，求下式的值：

$$\sum_{i=0}^{X} \sum_{j=[i=0]}^{Y} [i\&j = 0] \lfloor \log_2(i + j) + 1 \rfloor$$

对 $10^9 + 7$ 取模，其中：

• $\&$ 表示按位与运算；
• $[A]$ 在 $A$ 为真时等于 1，否则等于 0；
• $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含两个整数 $X, Y$ ($0 \le X, Y \le 10^9$)，表示一个测试用例。

输出格式

对于每个测试用例，输出一行，包含一个整数，即该测试用例的答案。

样例

输入格式 1

3
3 3
19 26
8 17

输出格式 1

14
814
278

说明

对于第一个测试用例：

• 两对 $(i, j)$ 使和增加 1：$(0, 1), (1, 0)$
• 六对 $(i, j)$ 使和增加 2：$(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0)$

因此答案为 $1 \times 2 + 2 \times 6 = 14$。