{"problem":{"name":"I. From Modular to Rational","description":{"content":"_This is an interactive problem._ Someone picked a positive rational number $x = p \\/ q$ where $1 <= p, q <= 10^9$. You may ask at most $10$ queries of the kind \"_? $m$_\", where $10^9 < m < 10^(12)$ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10235I"},"statements":[{"statement_type":"Markdown","content":"_This is an interactive problem._\n\nSomeone picked a positive rational number $x = p \\/ q$ where $1 <= p, q <= 10^9$. You may ask at most $10$ queries of the kind \"_? $m$_\", where $10^9 < m < 10^(12)$ and $m$ is a prime number. For each query, you will get the number $y$ such that $y equiv p q^(-1) pmod m$. You have to guess the number $x$.\n\nThe first line of input contains a single integer $t$, the number of test cases ($1 <= t <= 10^5$).\n\nFor each test case, you may ask at most $10$ queries. Each query should be one of two types: \n\nIn the example, you deal with $x = 1 \\/ 1$, $x = 1 \\/ 2$, and $x = 2 \\/ 1$, while always taking $m = 10^9 + 7$. \n\nAs you may see, it is not necessary to have $gcd (p, q) = 1$ as long as $1 <= p, q <= 10^9$ and $x = p \\/ q$.\n\n## Interaction\n\nThe first line of input contains a single integer $t$, the number of test cases ($1 <= t <= 10^5$).For each test case, you may ask at most $10$ queries. Each query should be one of two types:   \"_? $m$_\", where $10^9 < m < 10^(12)$ and $m$ is a prime number,  \"_! $p$ $q$_\", where $1 <= p, q <= 10^9$, meaning that the answer is equal to $p \\/ q$.  It is guaranteed that the number $x$ in each test case does not change during testing.\n\n[samples]\n\n## Note\n\nIn the example, you deal with $x = 1 \\/ 1$, $x = 1 \\/ 2$, and $x = 2 \\/ 1$, while always taking $m = 10^9 + 7$. As you may see, it is not necessary to have $gcd (p, q) = 1$ as long as $1 <= p, q <= 10^9$ and $x = p \\/ q$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, an unknown rational number $ x = \\frac{p}{q} \\in \\mathbb{Q} $ is fixed, with $ p, q \\in \\mathbb{Z} $, $ 1 \\leq p, q \\leq 10^9 $.  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq 10^5 $  \n2. For each test case, at most $ 10 $ queries are allowed.  \n3. Each query specifies a prime modulus $ m $ such that $ 10^9 < m < 10^{12} $.  \n4. For each query $ m $, the response is $ y \\equiv p \\cdot q^{-1} \\pmod{m} $, where $ q^{-1} $ denotes the modular inverse of $ q $ modulo $ m $.  \n\n**Objective**  \nReconstruct the unique rational number $ x = \\frac{p}{q} $ satisfying $ 1 \\leq p, q \\leq 10^9 $, using at most 10 modular queries per test case.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10235I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}