Інтерактивне вгадування факторіала

О ні, це зловісне журі знову щось приховує від вас, і вам доведеться здогадатися про це інтерактивно.

Цього разу вам потрібно знайти ціле число $n$. Для цього ви можете задати не більше $10$ запитів виду "Яка $k$-та десяткова цифра добутку всіх цілих чисел від $1$ до $n$ (також відомого як факторіал і позначається як $n!$)?"

Протокол взаємодії

Протокол взаємодії У першому рядку міститься ціле число $t(1\le t\le 100)$ — кількість тестів. Для кожного тесту ціле число $n$ вибирається заздалегідь. Довжина $n!$ не перевищує $20000$, тому $1\le n\le 5982$. Ви можете задати не більше $10$ запитів виду "? k" $(0\le k<20000)$. У відповідь на запит ви отримаєте одну цифру — $k$-ту десяткову цифру $n!$ (відповідь знаходиться в діапазоні від $0$ до $9$ включно). Цифри нумеруються з $0$, починаючи з найменш значущої цифри. Якщо $n!$ занадто короткий, і $k$-ї цифри немає, то буде повернено $0$.

Після того як ваша програма знайде значення $n$, вона повинна відповісти "! n". Якщо відповідь правильна, то ви отримаєте "YES" і повинні перейти до наступного тесту або завершити, якщо це був останній. Якщо відповідь неправильна, або ви намагаєтеся вгадати, і існує кілька можливих відповідей, що узгоджуються з отриманою інформацією, то ви отримаєте "NO". У цьому випадку ваше рішення отримає вердикт "Wrong answer", і ваш код буде негайно завершено.

Приклади