SOLVE
LATER
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:
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.
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 $$T$$ numbers, the answers to each problem.
For all subtasks:
$$T ≤ 10^4$$
$$1 ≤ y ≤ x$$
File 1 (70 pts)
$$x ≤ 100$$
File 2 (30 pts)
$$x ≤ 10^9$$
The base 2 results for the first four samples are as follows