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\)