Fortnite
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: combinatorics, constructive algorithms, games, greedy, hashing, interactive, math, number theory, strings

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.

Input format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
1

32

28

Example output:
? aa

? yb

! 31 59

Editorial:
The first query is $$$aa$$$, it can be used to find out $$$p$$$.
The second query is $$$zzzzzzzzzz$$$, let's calculate its hash without modulus, denote h_1, hash with modulus denote a1. Suppose we get a string with hash without modulus from $$$h_1 - a_1 - m$$$ to $$$h_1 - a_1 - 1$$$, then if we query it, we can easily find out the modulus.
Let's find such a string. To do this, let's write $$$h_1$$$ in $$$p$$$-ary number system, we get $$$26, 26, .... 26$$$, and also write $$$(a1 + 1)$$$ in $$$p$$$-ary notation. Subtract the second one from the first one without transfers, take the leftmost position, where we get $$$< 1$$$, and put there and in all the left $$$26$$$, as long as the number on the left is $$$1$$$, put $$$26$$$ in it and stand in it, when the number on the left is not $$$1$$$, we just subtract 1 from it. After that we translate it all back into a string.
It is claimed that this string fits, let's prove it. Its hash without modulus is obviously not greater than $$$h_1 - a_1 - 1$$$. Let's consider $$$2$$$ digits, the one in which we made $$$-1$$$ and $$$1$$$ to the left, let the number of the left digit $$$i$$$, then $$$a_1 + 1 \geq 25 * p^i$$$, and we subtracted less than $$$p^{i + 1} - 25 * p^i$$$, less because either in $$$i$$$ that digit was $$$0$$$, or $$$0$$$ was somewhere to the left, so there could be no equality, $$$p \leq 50$$$ by convention, $$$\geq p^{i + 1} - 25 * p^i \leq 50 * p^i - 25 * p^i = 25 * p^i \leq a_1 + 1$$$ => we subtracted less than $$$a_1 + 1$$$ => not more than $$$a_1$$$ => less than m. Let's denote what we subtracted by $$$x$$$, then our hash is $$$h_1 - a_1 - 1 - x = h_1 - a_1 - (x + 1)$$$. $$$x < m$$$ => $$$x + 1 \leq m$$$ => $$$hash \geq h1 - a1 - m$$$, which is what we needed to prove.