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