{"raw_statement":[{"iden":"problem statement","content":"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.\nYou 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$.\nProcess all the queries. Here, the Euclidean step count of a pair of two non-negative integers $(a,b)$ is defined as follows:\n\n*   $(a,b)$ and $(b,a)$ have the same Euclidean step count.\n*   $(0,a)$ has a Euclidean step count of $0$.\n*   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$."},{"iden":"constraints","content":"*   $1 ≤ Q ≤ 3 × 10^5$\n*   $1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$Q$\n$X_1$ $Y_1$\n$:$\n$X_Q$ $Y_Q$"},{"iden":"sample input 1","content":"3\n4 4\n6 10\n12 11"},{"iden":"sample output 1","content":"2 4\n4 1\n4 7\n\nIn the first query, $(2,3)$, $(3,2)$, $(3,4)$ and $(4,3)$ have a Euclidean step count of $2$. No pairs have a step count of more than $2$.\nIn the second query, $(5,8)$ has a Euclidean step count of $4$.\nIn the third query, $(5,8)$, $(8,5)$, $(7,11)$, $(8,11)$, $(11,7)$, $(11,8)$, $(12,7)$ have a Euclidean step count of $4$."},{"iden":"sample input 2","content":"10\n1 1\n2 2\n5 1000000000000000000\n7 3\n1 334334334334334334\n23847657 23458792534\n111111111 111111111\n7 7\n4 19\n9 10"},{"iden":"sample output 2","content":"1 1\n1 4\n4 600000013\n3 1\n1 993994017\n35 37447\n38 2\n3 6\n3 9\n4 2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}