---{"category_name":"easy","problem_code":"FINDMOD","problem_name":"Find the Modulus","problemComponents":{"constraints":"- $1 \\leq T \\leq 100$\n- $1 \\leq N \\leq 10^{18}$\n- $0 \\leq X \\leq 2 \\cdot 10^{18}$","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"","inputFormatState":false,"outputFormat":"In each testcase output $N$, the modulus the jury is thinking of.","outputFormatState":false,"sampleTestCases":{"0":{"id":1,"input":"2\n5\n0\n4\n5","output":"? 5\n? 6\n! 6\n? 4\n? 5\n! 39","explanation":"- **Test case $1$:** Jury\u0027s secret number is $N=6$. Your first query is $X=5$, so the jury returns $5 \\bmod 6 = 5$. Your second query is $X=6$, so the jury returns $6 \\bmod 6 = 0$. Finally, you output $6$ as the final answer, which is the correct answer.\n- **Test case $2$:** Jury\u0027s secret number is $N=39$. Your first query is $X=4$, so the jury returns $4 \\bmod 39 = 4$. Your second query is $X=5$, so the jury returns $5 \\bmod 39 = 5$. Finally, you output $39$ as the final answer, which is the correct answer (but a completely wild guess).\n\nNote that the jury does not output anything other than the answers to the queries, so please start asking queries for the next test case after outputting $N$ for the previous test case.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/Gu--bpznTRI","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"agnimandur","problem_tester":"","date_added":"21-10-2021","tags":{"0":"agnimandur","1":"cook134","2":"easy","3":"interactive"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/FINDMOD","time":{"view_start_date":1635100202,"submit_start_date":1635100202,"visible_start_date":1635100202,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=FINDMOD","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Mandarin](https://www.codechef.com/download/translated/COOK134/mandarin/FINDMOD.pdf), [Bengali](https://www.codechef.com/download/translated/COOK134/bengali/FINDMOD.pdf), and [Russian](https://www.codechef.com/download/translated/COOK134/russian/FINDMOD.pdf) as well.The jury has a secret number $N$, where $1 \le N \le 10^{18}$. You want to know this number, and you are allowed to ask the jury some queries. In each query, you give the jury a number $X$ where $0 \le X \le 2 \cdot 10^{18}$, and the jury tells you $X \mod{N}$.Please find $N$ using at most **two** queries per test case.### Interaction Format- The first line of contains $T$ - the number of test cases.- For each test case, you are allowed to allowed to ask the jury **at most two queries**. To make a query, output `? X` on one line; the jury will return the value of $x \mod {N}$ to the input for you to read.- In the case you exceed the number of queries, the judge will exit with the Wrong Answer verdict.- Once you have found the answer, output `! N` on one line. This **does not count** as a query.- If you output the wrong value for $N$, the judge will exit with the Wrong Answer verdict; if you output the correct value for $N$, the judge will **silently** continues. This means you should start asking queries for the next test case right after outputting the value of $N$ for the previous test case.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>