CF2096G.Wonderful Guessing Game

这是一道交互题。

你是千年科学学校的一名自豪的教师。今天，一名叫 Alice 的学生向你发起了一个猜数游戏的挑战。

Alice 心中想着一个 $1$ 到 $n$ 之间的整数，你必须通过向她提出一些查询来猜出这个数。

为了增加难度，她要求你必须先提出所有查询，而她将忽略其中的恰好 $1$ 个查询。

对于每个查询，你需要选择一个由 $1$ 到 $n$ 之间的 $k$ 个不同整数组成的数组，其中 $k$ 是偶数。然后，Alice 会给出以下回应之一：

• $\texttt{L}$：这个数位于数组的前 $\frac{k}{2}$ 个元素中；
• $\texttt{R}$：这个数位于数组的后 $\frac{k}{2}$ 个元素中；
• $\texttt{N}$：这个数不在数组中；
• $\texttt{?}$：这个查询被忽略。

Alice 很没耐心，因此你必须找到一种策略，使得查询次数最少。你能做到吗？

形式化地说，设 $f(n)$ 为确定 Alice 的数字所需的最小查询次数。你需要找到一种恰好使用 $f(n)$ 次查询的策略。

注意，交互器是自适应的，这意味着 Alice 的数字并非一开始就固定，可能会根据你的查询而变化。然而，保证至少存在一个数字与 Alice 的回应一致。

我们可以证明，对于所有满足 $2 \le n \le 2 \cdot 10^5$ 的 $n$，$f(n) \leq 20$。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的唯一一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——Alice 的数字的最大可能值。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

交互开始时，先读取整数 $n$。

然后，输出一个整数 $q$（$1 \leq q \leq 20$）——查询的次数。

要提出一个查询，请按以下格式输出一行：

• $k\,a_1\,a_2 \ldots a_k$（$2 \leq k \leq n$，$k$ 是偶数，$1 \leq a_i \leq n$，$a_i$ 互不相同）——数组的长度和数组本身。

在提出所有 $q$ 次查询后，读取一个字符串 $s$（$|s| = q$）——Alice 对查询的回应，如上所述。

当你确定 Alice 的数字时，输出一个整数 $x$（$1 \leq x \leq n$）——这个数字的值。

然后，继续处理下一个测试用例，如果没有更多测试用例，则终止程序。

在输出所有 $q$ 次查询后，不要忘记输出换行并刷新输出。否则，你将得到 Idleness limit exceeded。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• 其他语言的类似方法。

注意，即使你正确猜出了 Alice 的数字，但如果使用的查询次数超过了 $f(n)$，你也会得到 Wrong answer。

本题禁用 hack。

在第一个测试用例中，$n = 3$。我们提出了 $2$ 次查询：$[1, 2]$ 和再次的 $[1, 2]$。

• 对于第一次查询，Alice 的回应是 $\texttt{?}$，表示这次查询被忽略。
• 对于第二次查询，Alice 的回应是 $\texttt{N}$，表示她的数字不在数组 $[1, 2]$ 中。

根据以上信息，我们可以确定 Alice 的数字是 $3$。

可以证明，对于 $n = 3$，所有有效策略至少需要 $2$ 次查询。

在第二个测试用例中，$n = 5$。我们提出了 $3$ 次查询：$[3, 2, 4, 1]$、$[5, 4, 3, 1]$ 和 $[1, 5, 3, 4]$。

• 对于第一次查询，Alice 的回应是 $\texttt{R}$，表示她的数字在数组 $[4, 1]$ 中。
• 对于第二次查询，Alice 的回应是 $\texttt{?}$，表示这次查询被忽略。
• 对于第三次查询，Alice 的回应是 $\texttt{L}$，表示她的数字在数组 $[1, 5]$ 中。

根据以上信息，我们可以确定 Alice 的数字是 $1$。

可以证明，对于 $n = 5$，所有有效策略至少需要 $3$ 次查询。

翻译由 DeepSeek V3 完成