{"problem":{"name":"Kenus the Ancient Greek","description":{"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. You are given ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc015_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 ≤ Q ≤ 3 × 10^5$\n*   $1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$Q$\n$X_1$ $Y_1$\n$:$\n$X_Q$ $Y_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc015_f","tags":[],"sample_group":[["3\n4 4\n6 10\n12 11","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$."],["10\n1 1\n2 2\n5 1000000000000000000\n7 3\n1 334334334334334334\n23847657 23458792534\n111111111 111111111\n7 7\n4 19\n9 10","1 1\n1 4\n4 600000013\n3 1\n1 993994017\n35 37447\n38 2\n3 6\n3 9\n4 2"]],"created_at":"2026-03-03 11:01:14"}}