Gennady is an aspiring programmer. He is currently learning the Euclidean algorithm for computing the greatest common divisor of two positive integers.

Unfortunately, Gennady sometimes confuses the integer division operator (denoted by \t{div}) with the remainder operator (denoted by \t{mod}). As an example, $37$ \t{div} $10 = 3$ and $37$ \t{mod} $10 = 7$.

Here's Gennady's latest implementation of the Euclidean algorithm:

\begin{itemize}
\item \textit{Input: two positive integers $x$ and $y$.}

\item \textit{While $y > 0$:}

\, \, \, \textit{Set $x = x$ \t{div} $y$, then swap $x$ and $y$.}

\item \textit{Output: $x$.}

\end{itemize}

As you can see, if Gennady used the \t{mod} operator instead of the \t{div} operator, his implementation would be correct: the algorithm above would successfully find the greatest common divisor of $x$ and $y$. However, it turns out that even with this nasty bug the algorithm sometimes works correctly! 

You are given an integer $n$. Gennady is interested in finding all input pairs $(x, y)$ such that $1 \le x, y \le n$, the algorithm finishes, and produces the correct output. Let $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$ be all such pairs in lexicographic order (for all $1 \le i < k$, either $x_i < x_{i+1}$, or $x_i = x_{i+1}$ and $y_i < y_{i+1}$).

You are also given $q$ queries. Query $i$ is a positive integer $p_i$, and you should print $x_{p_i}$ and $y_{p_i}$, or report that $p_i > k$.
