{"raw_statement":[{"iden":"statement","content":"**This is an interactive problem. In the interaction section below you will find the information about flushing the output.**\n\nThe New Year tree of height _h_ is a perfect binary tree with vertices numbered 1 through 2_h_ - 1 in some order. In this problem we assume that _h_ is at least 2. The drawing below shows one example New Year tree of height 3:\n\nPolar bears love decorating the New Year tree and Limak is no exception. To decorate the tree, he must first find its root, i.e. a vertex with exactly two neighbours (assuming that _h_ ≥ 2). It won't be easy because Limak is a little bear and he doesn't even see the whole tree. Can you help him?\n\nThere are _t_ testcases. In each testcase, you should first read _h_ from the input. Then you can ask at most 16 questions of format \"_? x_\" (without quotes), where _x_ is an integer between 1 and 2_h_ - 1, inclusive. As a reply you will get the list of neighbours of vertex _x_ (more details in the \"Interaction\" section below). For example, for a tree on the drawing above after asking \"_? 1_\" you would get a response with 3 neighbours: 4, 5 and 7. Your goal is to find the index of the root _y_ and print it in the format \"_! y_\". You will be able to read _h_ for a next testcase only after printing the answer in a previous testcase and flushing the output.\n\nEach tree is fixed from the beginning and it doesn't change during your questions."},{"iden":"input","content":"The first line of the input contains a single integer _t_ (1 ≤ _t_ ≤ 500) — the number of testcases.\n\nAt the beginning of each testcase you should read from the input a single integer _h_ (2 ≤ _h_ ≤ 7) — the height of the tree. You can't read the value of _h_ in a next testcase until you answer a previous testcase."},{"iden":"interaction","content":"To ask a question about neighbours of vertex _x_, print \"_? x_\" (without quotes) on a separate line. Note, you must print an end-of-line character after the last character of the line and flush your output to get a response.\n\nThe response will consist of two lines. The first line will contain a single integer _k_ (1 ≤ _k_ ≤ 3) — the number of neighbours of vertex _x_. The second line will contain _k_ distinct integers _t_1, ..., _t__k_ (1 ≤ _t_1 < ... < _t__k_ ≤ 2_h_ - 1) — indices of neighbours of vertex _x_, gives in the increasing order.\n\nAfter asking at most 16 questions you have to say _y_ — the index of the root. Print \"_! y_\" (without quotes) and an end-of-line character, and flush the output.\n\nEach tree is fixed from the beginning and it doesn't change during your questions.\n\nYou can get _Idleness Limit Exceeded_ if you don't print anything or if you forget to flush the output.\n\nTo flush you can use (just printing a query/answer and end-of-line):\n\n* _fflush(stdout)_ in C++;\n* _System.out.flush()_ in Java;\n* _stdout.flush()_ in Python;\n* _flush(output)_ in Pascal;\n* See the documentation for other languages.\n\nIn any moment if the program reads _h_ = 0 or _k_ = 0 it should immediately terminate normally (for example, calling exit(0)). It means that the system detected incorrect request/output from your program and printed 0 because if can't process your requests anymore. In this case you'll receive verdict \"Wrong Answer\", but if you ignore case _h_ = 0 or _k_ = 0 it could lead to \"Runtime Error\", \"Time/Memory limit exceeded\" or any other verdict because your program could read a trash from the closed input stream.\n\n**Hacking**. To hack someone, use the following format:\n\nThe first line should contain a single integer _t_ equal to 1 (only one testcase is allowed in hacks). The second line should contain a single integer _h_. Each of next 2_h_ - 2 lines should contain two distinct integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ 2_h_ - 1), denoting two nodes connected with an edge. The printed edges must form a perfect binary tree of height _h_.\n\nOf course, contestant programs will not be able to see this input."},{"iden":"examples","content":"Input\n\n1\n3\n3\n4 5 7\n2\n1 2\n1\n2\n\nOutput\n\n? 1\n? 5\n? 6\n! 5\n\nInput\n\n2\n2\n1\n3\n2\n1 2\n2\n1 2\n4\n3\n3 12 13\n\nOutput\n\n? 1\n? 3\n? 3\n! 3\n? 6\n! 1"},{"iden":"note","content":"In the first sample, a tree corresponds to the drawing from the statement.\n\nIn the second sample, there are two two testcases. A tree in the first testcase has height 2 and thus 3 vertices. A tree in the second testcase has height 4 and thus 15 vertices. You can see both trees on the drawing below.\n\n"}],"translated_statement":[{"iden":"statement","content":"*这是一个交互式问题。在下面的交互部分，你将找到关于刷新输出的信息。*\n\n高度为 #cf_span[h] 的新年树是一棵完美二叉树，其顶点编号为 #cf_span[1] 到 #cf_span[2h - 1]（顺序任意）。在本题中，我们假设 #cf_span[h] 至少为 #cf_span[2]。下图展示了一棵高度为 #cf_span[3] 的新年树示例：\n\n北极熊喜欢装饰新年树，Limak 也不例外。为了装饰这棵树，他必须先找到它的根，即一个恰好有两个邻居的顶点（假设 #cf_span[h ≥ 2]）。这并不容易，因为 Limak 是一只小熊，他甚至看不到整棵树。你能帮助他吗？\n\n共有 #cf_span[t] 个测试用例。在每个测试用例中，你首先应从输入中读取 #cf_span[h]。然后你可以最多询问 #cf_span[16] 次形如 \"_? x_\"（不含引号）的问题，其中 #cf_span[x] 是介于 #cf_span[1] 和 #cf_span[2h - 1] 之间的整数。作为回应，你将获得顶点 #cf_span[x] 的邻居列表（更多细节见下面的“交互”部分）。例如，对于上图中的树，在询问 \"_? 1_\" 后，你会得到包含 #cf_span[3] 个邻居的响应：#cf_span[4]、#cf_span[5] 和 #cf_span[7]。你的目标是找到根的索引 #cf_span[y] 并以格式 \"_! y_\" 输出。只有在输出上一个测试用例的答案并刷新输出后，你才能读取下一个测试用例的 #cf_span[h]。\n\n每棵树在开始时即已固定，且在你的询问过程中不会改变。\n\n输入的第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 500]）——测试用例的数量。\n\n每个测试用例开始时，你应从输入中读取一个整数 #cf_span[h]（#cf_span[2 ≤ h ≤ 7]）——树的高度。在回答前一个测试用例之前，你无法读取下一个测试用例的 #cf_span[h] 值。\n\n要询问顶点 #cf_span[x] 的邻居，请在单独一行打印 \"_? x_\"（不含引号）。注意，你必须在行末打印换行符并刷新输出以获取响应。\n\n响应将包含两行。第一行包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 3]）——顶点 #cf_span[x] 的邻居数量。第二行包含 #cf_span[k] 个互不相同的整数 #cf_span[t1, ..., tk]（#cf_span[1 ≤ t1 < ... < tk ≤ 2h - 1]）——顶点 #cf_span[x] 的邻居索引，按升序排列。\n\n在最多询问 #cf_span[16] 次后，你必须输出 #cf_span[y]——根的索引。打印 \"_! y_\"（不含引号），并添加换行符，然后刷新输出。\n\n每棵树在开始时即已固定，且在你的询问过程中不会改变。\n\n如果你不输出任何内容或忘记刷新输出，你可能会得到 _Idleness Limit Exceeded_。\n\n要刷新输出，你可以使用（仅打印查询/答案并添加换行符）：\n\n在 C++ 中：_fflush(stdout)_；\n在 Java 中：_System.out.flush()_；\n在 Python 中：_stdout.flush()_；\n在 Pascal 中：_flush(output)_；\n其他语言请参阅文档。\n\n在任何时刻，如果程序读取到 #cf_span[h = 0] 或 #cf_span[k = 0]，应立即正常终止（例如调用 exit(0)）。这意味着系统检测到你的程序有错误的请求/输出，并打印了 0，因为它无法再处理你的请求。此时你会得到 \"Wrong Answer\" 的评测结果；但如果你忽略 #cf_span[h = 0] 或 #cf_span[k = 0] 的情况，可能会导致 \"Runtime Error\"、\"Time/Memory limit exceeded\" 或其他评测结果，因为你的程序可能会从已关闭的输入流中读取垃圾数据。\n\n*黑客攻击*。要黑客攻击某人，请使用以下格式：\n\n第一行应包含一个整数 #cf_span[t]，值为 #cf_span[1]（黑客攻击中只允许一个测试用例）。第二行应包含一个整数 #cf_span[h]。接下来的 #cf_span[2h - 2] 行，每行包含两个不同的整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 2h - 1]），表示两个由边连接的节点。打印的边必须构成一棵高度为 #cf_span[h] 的完美二叉树。\n\n当然，参赛程序无法看到此输入。\n\n在第一个样例中，树对应于题面中的图示。\n\n在第二个样例中，有两个测试用例。第一个测试用例中的树高度为 #cf_span[2]，因此有 #cf_span[3] 个顶点。第二个测试用例中的树高度为 #cf_span[4]，因此有 #cf_span[15] 个顶点。你可以在下图中看到这两棵树。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 500]）——测试用例的数量。每个测试用例开始时，你应从输入中读取一个整数 #cf_span[h]（#cf_span[2 ≤ h ≤ 7]）——树的高度。在回答前一个测试用例之前，你无法读取下一个测试用例的 #cf_span[h] 值。"},{"iden":"interaction","content":"要询问顶点 #cf_span[x] 的邻居，请在单独一行打印 \"_? x_\"（不含引号）。注意，你必须在行末打印换行符并刷新输出以获取响应。响应将包含两行。第一行包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 3]）——顶点 #cf_span[x] 的邻居数量。第二行包含 #cf_span[k] 个互不相同的整数 #cf_span[t1, ..., tk]（#cf_span[1 ≤ t1 < ... < tk ≤ 2h - 1]）——顶点 #cf_span[x] 的邻居索引，按升序排列。在最多询问 #cf_span[16] 次后，你必须输出 #cf_span[y]——根的索引。打印 \"_! y_\"（不含引号），并添加换行符，然后刷新输出。每棵树在开始时即已固定，且在你的询问过程中不会改变。如果你不输出任何内容或忘记刷新输出，你可能会得到 _Idleness Limit Exceeded_。要刷新输出，你可以使用（仅打印查询/答案并添加换行符）：\n\n在 C++ 中：_fflush(stdout)_；\n在 Java 中：_System.out.flush()_；\n在 Python 中：_stdout.flush()_；\n在 Pascal 中：_flush(output)_；\n其他语言请参阅文档。\n\n在任何时刻，如果程序读取到 #cf_span[h = 0] 或 #cf_span[k = 0]，应立即正常终止（例如调用 exit(0)）。这意味着系统检测到你的程序有错误的请求/输出，并打印了 0，因为它无法再处理你的请求。此时你会得到 \"Wrong Answer\" 的评测结果；但如果你忽略 #cf_span[h = 0] 或 #cf_span[k = 0] 的情况，可能会导致 \"Runtime Error\"、\"Time/Memory limit exceeded\" 或其他评测结果，因为你的程序可能会从已关闭的输入流中读取垃圾数据。\n\n*黑客攻击*。要黑客攻击某人，请使用以下格式：\n\n第一行应包含一个整数 #cf_span[t]，值为 #cf_span[1]（黑客攻击中只允许一个测试用例）。第二行应包含一个整数 #cf_span[h]。接下来的 #cf_span[2h - 2] 行，每行包含两个不同的整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ 2h - 1]），表示两个由边连接的节点。打印的边必须构成一棵高度为 #cf_span[h] 的完美二叉树。\n\n当然，参赛程序无法看到此输入。"},{"iden":"examples","content":"输入\n1\n3\n3\n4 5 7\n2\n1 2\n1\n2\n\n输出\n? 1\n? 5\n? 6\n! 5\n\n输入\n2\n2\n1\n3\n2\n1 2\n2\n1 2\n4\n3\n3 12 13\n\n输出\n? 1\n? 3\n? 3\n! 3\n? 6\n! 1"},{"iden":"note","content":"在第一个样例中，树对应于题面中的图示。\n\n在第二个样例中，有两个测试用例。第一个测试用例中的树高度为 #cf_span[2]，因此有 #cf_span[3] 个顶点。第二个测试用例中的树高度为 #cf_span[4]，因此有 #cf_span[15] 个顶点。你可以在下图中看到这两棵树。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions** \nLet $ t \\in \\mathbb{Z} $ be the number of test cases. \nFor each test case $ k \\in \\{1, \\dots, t\\} $: \n- Let $ h_k \\in \\mathbb{Z} $ denote the height of the perfect binary tree, with $ 2 \\leq h_k \\leq 7 $. \n- Let $ V_k = \\{1, 2, \\dots, 2^{h_k} - 1\\} $ be the set of vertices. \n- Let $ G_k = (V_k, E_k) $ be the undirected perfect binary tree graph with fixed structure. \n- The **root** $ y_k \\in V_k $ is the unique vertex of degree 2. \n\n**Constraints** \n1. $ 1 \\leq t \\leq 500 $ \n2. For each test case $ k $: \n - $ 2 \\leq h_k \\leq 7 $ \n - The tree is a perfect binary tree on $ 2^{h_k} - 1 $ vertices. \n - The root has exactly two neighbors; all leaves have degree 1; all other internal nodes have degree 3. \n3. You may ask at most 16 queries per test case. \n4. Each query: ask for neighbors of vertex $ x \\in V_k $, receive sorted list of its adjacent vertices. \n\n**Objective** \nFor each test case $ k $, determine the root $ y_k \\in V_k $ (the unique vertex of degree 2) using at most 16 queries of the form `? x`, then output `! y_k`.","simple_statement":null,"has_page_source":false}