{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eThis is an interactive problem.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eWe have hidden an integer $$$1 \\le X \\le 10^{9}$$$. You \u003cspan class\u003d\"tex-font-style-bf\"\u003edon\u0027t have to\u003c/span\u003e guess this number. You have to \u003cspan class\u003d\"tex-font-style-bf\"\u003efind the number of divisors\u003c/span\u003e of this number, and you \u003cspan class\u003d\"tex-font-style-bf\"\u003edon\u0027t even have to find the exact number\u003c/span\u003e: your answer will be considered correct if its absolute error is not greater than 7 \u003cspan class\u003d\"tex-font-style-bf\"\u003eor\u003c/span\u003e its relative error is not greater than $$$0.5$$$. More formally, let your answer be $$$ans$$$ and the number of divisors of $$$X$$$ be $$$d$$$, then your answer will be considered correct if \u003cspan class\u003d\"tex-font-style-bf\"\u003eat least one\u003c/span\u003e of the two following conditions is true:\u003c/p\u003e\u003cul\u003e\u003cli\u003e $$$| ans - d | \\le 7$$$;\u003c/li\u003e\u003cli\u003e $$$\\frac{1}{2} \\le \\frac{ans}{d} \\le 2$$$.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYou can make at most $$$22$$$ queries. One query consists of one integer $$$1 \\le Q \\le 10^{18}$$$. In response, you will get $$$gcd(X, Q)$$$\u0026nbsp;— the greatest common divisor of $$$X$$$ and $$$Q$$$.\u003c/p\u003e\u003cp\u003eThe number $$$X$$$ is fixed before all queries. In other words, \u003cspan class\u003d\"tex-font-style-bf\"\u003einteractor is not adaptive\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eLet\u0027s call the process of guessing the number of divisors of number $$$X$$$ a \u003cspan class\u003d\"tex-font-style-it\"\u003egame\u003c/span\u003e. In one test you will have to play $$$T$$$ independent games, that is, guess the number of divisors $$$T$$$ times for $$$T$$$ independent values of $$$X$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains one integer $$$T$$$ ($$$1 \\le T \\le 100$$$)\u0026nbsp;— the number of games.\u003c/p\u003e"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cp\u003eTo make a query print a line \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e? Q\u003c/span\u003e\" ($$$1 \\le Q \\le 10^{18}$$$). After that read one integer $$$gcd(X, Q)$$$. You can make no more than $$$22$$$ such queries during one game.\u003c/p\u003e\u003cp\u003eIf you are confident that you have figured out the number of divisors of $$$X$$$ with enough precision, you can print your answer in \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e! ans\u003c/span\u003e\" format. $$$ans$$$ have to be an integer. If this was the last game, you have to terminate the program, otherwise you have to start the next game immediately. Note that the interactor doesn\u0027t print anything in response to you printing answer.\u003c/p\u003e\u003cp\u003eAfter printing a query do not forget to output end of line and flush the output. To do this, use:\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout.flush()\u003c/span\u003e in C++;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e in Java;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e in Pascal;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003estdout.flush()\u003c/span\u003e in Python;\u003c/li\u003e\u003cli\u003e see documentation for other languages.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eHacks\u003c/span\u003e\u003c/p\u003e\u003cp\u003eTo hack, use the following format:\u003c/p\u003e\u003cp\u003eThe first line contains one integer $$$T$$$ ($$$1 \\le T \\le 100$$$)\u0026nbsp;— the number of games.\u003c/p\u003e\u003cp\u003eEach of the next $$$T$$$ lines contains one integer $$$X$$$ ($$$1 \\le X \\le 10^{9}$$$)\u0026nbsp;— the hidden number.\u003c/p\u003e\u003cp\u003eSo the example has the form \u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e2\u003cbr\u003e998244353\u003cbr\u003e4194304\u003cbr\u003e\u003c/pre\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\n1\n\n1\n\n1\n\n\n1024\n\n1048576\n\n4194304\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n? 982306799268821872\n\n? 230856864650023977\n\n? 134690134760714371\n\n! 5\n? 1024\n\n? 1048576\n\n? 1073741824\n\n! 42\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eWhy the limitation for number of queries is 22 exactly? Maybe the problem author is a Taylor Swift fan.\u003c/p\u003e\u003cp\u003eLet\u0027s look at the example.\u003c/p\u003e\u003cp\u003eIn the first game $$$X \u003d 998\\,244\\,353$$$ is hidden. Would be hard to guess this, right? This number is prime, so the number of its divisors is 2. The solution has made several random queries, and all the responses turned out to be 1 (strange things, not even one of three random numbers is divisible by $$$998\\,244\\,353$$$). It\u0027s fare to assume that the hidden number doesn\u0027t have many divisors, so the solution has answered 5. Why not. This answer will be considered correct since $$$| 5 - 2 | \u003d 3 \\le 7$$$.\u003c/p\u003e\u003cp\u003eIn the second game $$$X \u003d 4\\,194\\,304 \u003d 2^{22}$$$ is hidden, it has 23 divisors. The solution has made queries $$$1024 \u003d 2^{10}$$$, $$$1\\,048\\,576 \u003d2^{20}$$$, $$$1\\,073\\,741\\,824 \u003d 2^{30}$$$ and got responses $$$1024 \u003d 2^{10}$$$, $$$1\\,048\\,576 \u003d2^{20}$$$, $$$4\\,194\\,304 \u003d 2^{22}$$$, respectively. Then the solution got completely confused and answered the answer to The Ultimate Question of Life, the Universe, and Everything. This answer will be considered correct since $$$\\frac{1}{2} \\le \\frac{42}{23} \\le 2$$$.\u003c/p\u003e"}}]}