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\ge N$ and $x\oplus y\le M$. Since the answer may be very large, output it modulo ${10}^9+7$.

There will be $T$ such test cases.

Constraints

$1\le T\le {10}^4$

$2\le N\le {10}^{18}$

$0\le M\le {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)$.