Este problema es interactivo.

Un programa tiene versiones \(1, 2, \dots, n\). A partir de cierta versión \(k\) todas son malas: las versiones \(1, \dots, k-1\) son buenas y \(k, \dots, n\) son malas. Tienes que encontrar \(k\) preguntando si una versión es mala, con a lo más 32 preguntas por caso.

Interacción

Primero lee \(T\) \((1 \le T \le 300)\), la cantidad de casos. Para cada caso:

• Lee \(n\) \((1 \le n \le 2^{31} - 1)\).
• Para preguntar por la versión \(x\) \((1 \le x \le n)\), imprime una línea ? x. El juez responde 1 si \(x\) es mala o 0 si es buena.
• Cuando sepas la respuesta, imprime ! k y pasa al caso siguiente.

Después de cada línea que imprimas, haz flush de la salida (fflush(stdout) en C, cout.flush() o endl en C++, System.out.flush() en Java, print(..., flush=True) en Python).

Ejemplo

En el primer caso \(n = 5\) y \(k = 4\); en el segundo, \(n = 1\) y la única versión es mala.

Basado en el problema 278 de LeetCode, First Bad Version, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.