Given two integers ~N~ and ~M~, count the number of ordered pairs of integers ~(x, y)~ in the range ~[1, N)~ such that ~x + y \geq N~ and ~x \oplus y \leq M~. Since the answer may be very large, output it modulo ~10^9 + 7~.

There will be ~T~ such test cases.

Constraints

~1 \leq T \leq 10^4~

~2 \leq N \leq 10^{18}~

~0 \leq M \leq 10^{18}~

Input Specification

The first line contains an integer ~T~.

The new ~T~ line contains two integers, ~N~ and ~M~.

Output Specification

Output a single integer, the number of pairs modulo ~10^9 + 7~.

Sample Input

1
5 6

Sample Output

8

Explanation for Sample

The pairs are ~(1, 4)~, ~(2, 3)~, ~(2, 4)~, ~(3, 2)~, ~(3, 3)~, ~(4, 1)~, ~(4, 2)~, ~(4, 4)~.