Let $P[0 \dots N-1]$ be a binary string of length N. Then let's define $S^{\infty}(P)$ as an infinite string with $S^{\infty}[i] = P[i\%N] \space \forall\space i ≥0$ (informally, $S^{\infty}(P)$ is the concatenation of P with itself an infinite number of times).

Define the GCD-string of two integers $a, b$, with $a \geq b$ to be a binary string of length a that satisfies the following:

• $g(a,b)$ = $100\dots 000$ (1 followed by $a-1$ zeros ) if a is divisible by b
• $g(a,b)$ = First a characters of $S^{\infty}(g(b, a \space mod\space b))$ otherwise

We can define $F(a,b)$ to be the value of the integer represented by the binary string $g(a,b)$ in base-2. Given T pairs of integers $(x,y)$, compute $F(x,y)\space mod\space 10^9+7$ for each pair.

Input Format:

The first line will contain the number of test cases T.
Each test case can be described with a single line containing two integers $x,y$.

Output Format:

Output T numbers, the answers to each problem.

Constraints

For all subtasks:
$T ≤ 10^4$
$1 ≤ y ≤ x$

File 1 (70 pts)
$x ≤ 100$

File 2 (30 pts)
$x ≤ 10^9$