This is an interactive problem.

While procrastinating at work, Dilhan the elf stumbled upon two arrays $a$ and $b$. Initially, both of them consist of a single integer $2^k$ (i.e., $a=b=[2^k]$), where $k$ is a non-negative integer.

Dilhan then applied the following two types of operations an arbitrary number of times (possibly zero), in any order:

1. Flatten — Choose either $a$ or $b$, and select any element $x$ that is maximal within that array ($x$ does not need to be maximal in the other array). Then, replace $x$ with two copies of $\frac x2$ in the same position. This operation can only be applied if $x$ is even.
2. Concatenate — Set both $a$ and $b$ to be $a+b$, where $+$ denotes array concatenation.

After performing these operations, Dilhan discards $b$, hides $a$ from you, and challenges you to a game.

Let $n$ be the length of the hidden array $a$. You may make the following query:

• Choose an interval $[l, r]$ ($1\le l\le r\le n$), and Dilhan will tell you the sum $a_l+a_{l+1}+\cdots+a_r$.

Determine the value of the maximum element of $a$ by making at most $300$ queries.

这是一个交互式问题。

精灵迪尔汉在工作时拖延，偶然发现了两个数组 $a$ 和 $b$。初始时，它们均仅包含一个整数 $2^k$（即 $a = b = [2^k]$），其中 $k$ 是一个非负整数。

随后，迪尔汉以任意顺序、任意次数（包括零次）执行以下两类操作：

1. 展平（Flatten） —— 任选数组 $a$ 或 $b$，并在该数组中选择一个极大元 $x$（即 $x$ 在所选数组中为最大值；它无需在另一数组中也为最大值）。然后将该位置上的 $x$ 替换为两个 $\frac{x}{2}$（即在原位置插入两个相等的副本）。该操作仅当 $x$ 为偶数时才可执行。
2. 拼接（Concatenate） —— 将 $a$ 和 $b$ 同时设为 $a + b$，其中 $+$ 表示数组拼接（即连接）。

执行完这些操作后，迪尔汉丢弃数组 $b$，并将数组 $a$ 隐藏起来，向你发起挑战。

设隐藏数组 $a$ 的长度为 $n$。你可以进行如下查询：

• 选择一个区间 $[l, r]$（满足 $1 \le l \le r \le n$），迪尔汉会告诉你子段和 $a_l + a_{l+1} + \cdots + a_r$。

你需要在至多 $300$ 次查询内，确定数组 $a$ 中最大元素的值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of $a$.

It is guaranteed that $1\le a_i\le 2^{30}$, and the array $a$ can be generated by the process described in the statements.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 表示数组 $a$ 的长度。

保证 $1\le a_i\le 2^{30}$，且数组 $a$ 可由题目描述中的过程生成。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

In the first test case, Dilhan's hidden array $a$ is $[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$. It can be generated by the following process:

Type

$a$ after operation

$b$ after operation

0

$[4]$

$[4]$

1

Flatten $a$

$[\underline 4] \to {[2, 2]}$

$[4]$

2

Flatten $b$

$[2, 2]$

$[\underline 4] \to {[2, 2]}$

3

Flatten $a$

$[2, \underline 2] \to {[2, 1, 1]}$

$[2, 2]$

4

Concatenate

$[2, 1, 1, 2, 2]$

$[2, 1, 1, 2, 2]$

5

Flatten $a$

$[\underline 2, 1, 1, 2, 2]\to {[1, 1, 1, 1, 2, 2]}$

$[2, 1, 1, 2, 2]$

6

Concatenate

$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$

$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$

• For the query $\mathtt{?\;3\;8}$, the jury responded with $1+1+2+2+2+1=9$;
• For the query $\mathtt{?\;1\;4}$, the jury responded with $1+1+1+1=4$;
• For the query $\mathtt{?\;5\;11}$, the jury responded with $2+2+2+1+1+2+2=12$.

And the value of the maximum element of $a$ is $2$.

In the second test case, the array $a$ has only one element. By the query, the value of the only element is $1$, and it must also be the maximum value.

In the third test case, Dilhan's hidden array $a$ is $[4, 4, 4, 4, 4, 4, 4, 4]$. It can be generated by the following process:

Type

$a$ after operation

$b$ after operation

0

$[4]$

$[4]$

1

Concatenate

$[4, 4]$

$[4, 4]$

2

Concatenate

$[4, 4, 4, 4]$

$[4, 4, 4, 4]$

3

Concatenate

$[4, 4, 4, 4, 4, 4, 4, 4]$

$[4, 4, 4, 4, 4, 4, 4, 4]$

And the value of the maximum element of $a$ is $4$.

In the fourth test case, Dilhan's hidden array $a$ is $[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$.

在第一个测试用例中，Dilhan 的隐藏数组 $a$ 为 $[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$。它可通过以下过程生成：

类型

操作后的 $a$

操作后的 $b$

0

$[4]$

$[4]$

1

展开 $a$

$[\underline 4] \to {[2, 2]}$

$[4]$

2

展开 $b$

$[2, 2]$

$[\underline 4] \to {[2, 2]}$

3

展开 $a$

$[2, \underline 2] \to {[2, 1, 1]}$

$[2, 2]$

4

拼接

$[2, 1, 1, 2, 2]$

$[2, 1, 1, 2, 2]$

5

展开 $a$

$[\underline 2, 1, 1, 2, 2]\to {[1, 1, 1, 1, 2, 2]}$

$[2, 1, 1, 2, 2]$

6

拼接

$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$

$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$

• 对于查询 $\mathtt{?\;3\;8}$，评测系统返回 $1+1+2+2+2+1=9$；
• 对于查询 $\mathtt{?\;1\;4}$，评测系统返回 $1+1+1+1=4$；
• 对于查询 $\mathtt{?\;5\;11}$，评测系统返回 $2+2+2+1+1+2+2=12$。

且数组 $a$ 中最大元素的值为 $2$。

在第二个测试用例中，数组 $a$ 仅含一个元素。通过查询可知该唯一元素的值为 $1$，它也必然是最大值。

在第三个测试用例中，Dilhan 的隐藏数组 $a$ 为 $[4, 4, 4, 4, 4, 4, 4, 4]$。它可通过以下过程生成：

类型

操作后的 $a$

操作后的 $b$

0

$[4]$

$[4]$

1

拼接

$[4, 4]$

$[4, 4]$

2

拼接

$[4, 4, 4, 4]$

$[4, 4, 4, 4]$

3

拼接

$[4, 4, 4, 4, 4, 4, 4, 4]$

$[4, 4, 4, 4, 4, 4, 4, 4]$

且数组 $a$ 中最大元素的值为 $4$。

在第四个测试用例中，Dilhan 的隐藏数组 $a$ 为 $[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$。