H. Guess the Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. You must flush the output after printing each line. For example, in C++ use fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output), and in Python — sys.stdout.flush().

Two players, A and B, are playing on a pile of $$$N$$$ stones. Player A moves first, and then they alternate turns. On each move, a player may remove any number of stones from $$$1$$$ to $$$k$$$, but not more than the number currently in the pile. A player who cannot move loses.

The value of $$$k$$$ is an unknown integer satisfying $$$1 \le k \le 1000$$$. Your task is to determine this unknown value.

You may ask queries. A query is a single integer $$$N$$$ ($$$1 \le N \le 10^{18}$$$). For this $$$N$$$, the system simulates optimal play and replies with "A" if player A wins, or "B" if player B wins.

You may ask at most $$$70$$$ queries (not counting the final answer).

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

Following lines will contain responses to your queries — "A" or "B". The $$$i$$$-th line is a response to your $$$i$$$-th query.

You can read a response only after printing a query and flushing the output.

Output

To ask a query, output "? n" (without quotes), where $$$1 \le n \le 10^{18}$$$, followed by a flush operation.

When you determine the unknown value $$$k$$$, output "! k" (without quotes), where $$$1 \le k \le 1000$$$, flush the output, and continue to the next test case.

Example
Input
1

A

B

A
Output

? 1

? 765

? 1000

! 50