H. Fortnite
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem!

Timofey is writing a competition called Capture the Flag (or CTF for short). He has one task left, which involves hacking a security system. The entire system is based on polynomial hashes$$$^{\text{∗}}$$$.

Timofey can input a string consisting of lowercase Latin letters into the system, and the system will return its polynomial hash. To hack the system, Timofey needs to find the polynomial hash parameters ($$$p$$$ and $$$m$$$) that the system uses.

Timofey doesn't have much time left, so he will only be able to make $$$3$$$ queries. Help him solve the task.

$$$^{\text{∗}}$$$ The polynomial hash of a string $$$s$$$, consisting of lowercase Latin letters of length $$$n$$$, based on $$$p$$$ and modulo $$$m$$$ is $$$(\mathrm{ord}(s_1) \cdot p ^ 0 + \mathrm{ord}(s_2) \cdot p ^ 1 + \mathrm{ord}(s_3) \cdot p ^ 2 + \ldots + \mathrm{ord}(s_n) \cdot p ^ {n - 1}) \bmod m$$$. Where $$$s_i$$$ denotes the $$$i$$$-th character of the string $$$s$$$, $$$\mathrm{ord}(\mathrm{chr})$$$ denotes the ordinal number of the character $$$\mathrm{chr}$$$ in the English alphabet, and $$$x \bmod m$$$ is the remainder of $$$x$$$ when divided by $$$m$$$.

Input

Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

It is guaranteed that the $$$p$$$ and $$$m$$$ used by the system satisfy the conditions: $$$26 < p \leq 50$$$ and $$$p + 1 < m \leq 2 \cdot 10^9$$$.

Interaction

To make a query to the system, output ? $$$s$$$, where $$$s$$$ is a string of no more than $$$50$$$ characters in length, the hash of which you want to know. In response to this query, you will receive the polynomial hash of the string $$$s$$$.

To output the answer, output ! $$$p$$$ $$$m$$$, where $$$p$$$ is the base of the hash, and $$$m$$$ is the modulus. After that, immediately proceed to the next test case.

You have to make not more than $$$3$$$ queries ?, otherwise you will get verdict Wrong Answer.

After outputting a query, do not forget to output a newline and flush the output buffer. Otherwise, you will receive the verdict Idleness limit exceeded. To flush the buffer, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
1

32

28
Output
? aa

? yb

! 31 59
Note

Answer for the first query is $$$(ord(a) \cdot 31^0 + ord(a) \cdot 31^1) \mod 59 = (1 + 1 \cdot 31) \mod 59 = 32$$$.

Answer for the second query is $$$(ord(y) \cdot 31^0 + ord(b) \cdot 31^1) \mod 59 = (25 + 2 \cdot 31) \mod 59 = 28$$$.