题目背景

本题比较考验码力。

前段时间，PC 在练习以 dfs 和 bfs 为主的搜索算法，感到些许棘手——以至于某次睡梦中，他梦到了一个大法师。

大法师感受到了他的疲惫，于是丢给了他一个小游戏玩，其名为 1A2B。但这款游戏需要两个人一起游玩，而大法师忙着处理别的事情，于是 PC 决定和你来一起玩这个小游戏。

让我们把这个小游戏抽象为一个问题吧。

这是一道交互题。

注意，请在输出之后，加一行 $\mathtt{flush}$。

下面给出 $\text{C, C++, Java, Python}$ 的输出方式：

1. $\text{C}$

   printf("! 1234");
   fflush(stdout);
   

2. $\text{C++}$

   cout << "!" << 1234 << '\n';
   cout.flush();
   

3. $\text{Java}$

   System.out.println("! 1234");
   System.out.flush();
   

4. $\text{Python}$

   print("! 1234")
   stdout.flush()
   

题目描述

每次游戏开始时，PC 会在心里想出一个四位数 $x$。

$x$ 可能 包含前导 $0$，但保证 $x$ 由 $[0, 9]$ 中 不同 的四个数字组成。比如说，$0148, 1234$ 是合法的，$1145, 0001$ 是不合法的。

你可以随意想一个四位数 $y$ 然后告诉 PC，PC 会根据你的询问，回答你一个字符串，字符串按照 $\mathtt{p}A\mathtt{q}B$ 的格式给出。

询问的四位数 $y$ 也可以包含前导 $0$，且没有类似于 $x$ 的 由不同数字组成 的限制。

回答中的 $\mathtt{p, q}$ 是根据以下规则来确定的：

1. 遍历 $y$ 的每一位数字；
2. 每有一位数字 位置相同且值相同，则 $\mathtt{p}$ 加一；
3. 每有一位数字 位置不相同但值相同，则 $\mathtt{q}$ 加一

比如：

$x = 1347, y = 3456$，你将会得到 $\mathtt{0}A\mathtt{2}B$，因为 $y$ 中的数字 $3, 4$ 在 $x$ 中 都出现了，但是位置都不相同。

$x = 0412, y = 0721$，你将会得到 $\mathtt{1}A\mathtt{2}B$，因为 $y$ 中的数字 $0, 2, 1$ 在 $x$ 中都出现了，但是 $0$ 对应的位置 相同，$2, 1$ 对应的位置 不相同。

$x = 1234, y = 1212$，你将会得到 $\mathtt{2}A\mathtt{2}B$，因为 $y$ 中的数字 $1, 2, 1, 2$ 在 $x$ 中都出现了，但是前两个 $1, 2$ 对应的位置 相同，后两个 $1, 2$ 对应的位置 不相同。

还是没听懂？可以 点击这里 尝试一下！

显然，只要询问次数够多，猜对指定的数字是很容易的。所以，PC 想考考你，如何在最多 $15$ 次询问里，确定具体的四位数字呢？

有趣的是，$15$ 次绝对不是最优解，但是本题放宽了限制。

交互方式

本题有多组测试用例。

首先，你需要读入一行整数 $t$，代表测试用例的数量。

接下来，对于每个测试用例，你需要进行最多 $15$ 次询问，并确定答案。

对于一次询问，输出 ? y，代表你给 PC 的四位数字 $y$。

接下来，读入一个字符串 $v$，如果 $v$ 不为 ok，代表 $y$ 不是四位数字 或 询问次数超过了 $15$ 次，此时你需要立刻退出程序以得到 Wrong Answer 判定，否则你会遇到其他任意可能的评测结果。如果 $v$ 为 ok，请继续接下来的读入。

接下来，读入一个字符串 $\mathtt{p}A\mathtt{q}B$，代表 PC 的回复，并进行你的下一步计算。

如果你能唯一确定答案，输出 ! x，代表 PC 的数字 $x$。

同样的，你需要读入一个字符串 $v$，如果 $v$ 不为 ok，代表你猜错了，此时你需要立刻退出程序以得到 Wrong Answer 判定，否则你会遇到其他任意可能的评测结果。如果 $v$ 为 ok，请继续接下来的读入。

只要你的答案是正确的，你就会得到 Accepted 判定。

如果你没有在输出后 $\mathtt{flush}$，你将会得到除 Accepted 之外的其他任意评测结果。

2

ok
3A0B

ok
2A1B

ok

ok
0A3B

ok
2A1B

ok
3A0B

ok

? 2738


? 2734


! 2748

? 9782


? 7829


? 7892


! 7895

提示

样例 1 说明

在第一个测试用例中，$x = 2748$

玩家给出了询问 $y = 2738$，$2, 7, 8$ 在 $x$ 中出现了，且位置均相同，因此返回 $\mathtt{3}A\mathtt{0}B$。

玩家给出了询问 $y = 2734$，$2, 7, 4$ 在 $x$ 中出现了，且 $2, 7$ 对应的位置相同，$4$ 对应的位置不相同，因此返回 $\mathtt{2}A\mathtt{1}B$。

此时，$4$ 个位置的数字都已确定，从而玩家确定答案为 $x = 2748$。

请注意，样例的询问方式和游玩方式似乎很愚蠢，所以它也许只是一个形象化的例子。

数据规模与约定

对于全部的测试点，保证 $1 \leq t \leq 10 ^ 4$，且满足：

1. $x$ 可能包含前导 $0$，但保证 $x$ 由 $[0, 9]$ 中不同的四个数字组成。
2. 询问的四位数 $y$ 也可以包含前导 $0$，且没有类似于 $x$ 的 由不同数字组成 的限制。