提示

这是一道交互题。

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

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

1. $\mathtt{C}$

   printf("%d", 1234);
   fflush(stdout);
   

2. $\mathtt{C++}$

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

3. $\mathtt{Java}$

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

4. $\mathtt{Python}$

   print(1234)
   stdout.flush()
   

题目背景

众所不周知，Ocean 和 PC 每个月都会结伴从旗山校区骑车出发去打卡仓山校区、保养自行车以及发际线。由于来回一趟需要约 $46$ $km$ 的路程，他们每次都会选择在下午出发，在外面吃完晚饭，最后赶在门禁前回到旗山校区。

通常来说，这顿在外面的晚饭都是 AA 制的。直到某次途中聊天时，Ocean 聊到了刚发下来的奖学金，PC 打趣地说: "那太好了兄弟，为了庆祝你顺利拿到奖学金，就奖励你今天请我吃晚饭吧!"。此时已经做好挨骂准备的 PC 却没想到，Ocean 对此的回应是: "你都喊兄弟了，那还说啥了，这饭我请你吃就完了呗。"

这扯不扯呢你说。最终 PC 因为不好意思，决定跟 Ocean 玩个猜数字的小游戏，谁输了今天的晚饭就谁请！

题目描述

Ocean 会在脑海中随机想一个整数 $x$，$-10^6 \leq x \leq 10^6$，让 PC 去猜 $x$ 的值。PC 可以猜测任意一个数字 $y$，Ocean 会告诉 PC 这个 $y$ 与 $x$ 的大小关系，即大于小于或是等于。显然在最多 $2 \times 10^6$ 次询问后，PC 就能猜出 Ocean 想的数字 $x$。但肯定没有这么多时间让 PC 来猜 $2 \times 10^6$ 次！Ocean 思考片刻，突然想起来今年是他的 $21$ 岁生日！于是他决定如果 PC 能在最多 $21$ 次猜测内猜对自己想的数字 $x$，就算他获得游戏胜利。

那么，如果你是 PC，你能在最多 $21$ 次猜测内猜对 Ocean 想的数字 $x$ 吗？

交互

本题有多组测试用例。

第 $1$ 行需要读入一个整数 $t$，代表测试用例的数量。

接下来，对于每个测试用例，你需要在最多 $21$ 次猜测内猜出 Ocean 选出的数字 $x$。

对于一次猜测，输出一个整数 $y$，代表你本次猜的数字为 $y$。注意 $y$ 必须满足 $-10^6 \leq y \leq 10^6$，否则你会得到 Wrong Answer 判定。

随后，读入一个数字 $a \in [-1, 0, 1]$，分别代表 $y < x$，$y = x$ 和 $y > x$。若 $a = 0$ 则代表你已猜对本次的 $x$，可以开始下一个 $x$ 的猜测。否则，根据得到的大小关系进行你的下一步猜测，直到 $a = 0$ 为止。

如果你总的猜测次数足够少，且猜出了每一个数字，你就会得到 Accepted 判定。

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

2

1

-1

0

0

10

8

9

233

提示

样例中，要猜 $2$ 个不同的 $x$。其中：

1. 对于第 $1$ 个 $x$，我们首先猜数字 $10$，得到的判定是数字 $1$，说明 $10 > x$；然后我们再猜数字 $8$，得到的判定是数字 $-1$，说明 $8 < x < 10$。由于 $x$ 是整数，我们可以确认 $x = 9$。所以我们输出 $9$，得到判定数字 $0$，结束本轮猜测。
2. 对于第 $2$ 个 $x$，我们首先猜数字 $233$，得到的判定是数字 $0$，说明 $x = 233$，一发入魂了！直接结束本轮猜测。

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^3$，$-10^6 \leq x_i \leq 10^6$。