Problem Statement

Kenus, the organizer of International Euclidean Olympiad, is seeking a pair of two integers that requires many steps to find its greatest common divisor using the Euclidean algorithm.

You are given $Q$ queries. The $i$-th query is represented as a pair of two integers $X_i$ and $Y_i$, and asks you the following: among all pairs of two integers $(x,y)$ such that $1 ≤ x ≤ X_i$ and $1 ≤ y ≤ Y_i$, find the maximum Euclidean step count (defined below), and how many pairs have the maximum step count, modulo $10^9+7$.

Process all the queries. Here, the Euclidean step count of a pair of two non-negative integers $(a,b)$ is defined as follows:

• $(a,b)$ and $(b,a)$ have the same Euclidean step count.
• $(0,a)$ has a Euclidean step count of $0$.
• If $a > 0$ and $a ≤ b$, let $p$ and $q$ be a unique pair of integers such that $b=pa+q$ and $0 ≤ q < a$. Then, the Euclidean step count of $(a,b)$ is the Euclidean step count of $(q,a)$ plus $1$.

Constraints

• $1 ≤ Q ≤ 3 × 10^5$
• $1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)$

Input

The input is given from Standard Input in the following format:

Q
X_1 Y_1
:
X_Q Y_Q

Output

For each query, print the maximum Euclidean step count, and the number of the pairs that have the maximum step count, modulo $10^9+7$, with a space in between.