Загадано ціле число (1 \le n < 10^8), яке не ділиться на . Вам потрібно знайти це число.
Ви можете задавати запити такого вигляду: вибрати ціле число (1 \le x \le 10^9). У відповідь ви отримаєте першу цифру числа n \cdot x.
Першою цифрою додатного цілого числа називається його найстарша цифра у десятковому записі. Наприклад, перша цифра чисел , , дорівнює відповідно , , .
Вам потрібно знайти загадане число . Максимально можна використовувати запитів на кожен набір вхідних даних.
Перший рядок містить два цілі числа і (1 \le t \le 10^3, q=28) — кількість наборів вхідних даних та максимальну кількість запитів, які можна використати в кожному наборі вхідних даних.
У кожному наборі вхідних даних загадано окреме число .
Щоб зробити запит, виведіть «», де 1 \le x \le 10^9.
У відповідь на запит програма журі виведе одне ціле число (1 \le d \le 9) — першу цифру числа n \cdot x.
Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. В іншому випадку ви отримаєте вердикт Вичерпано ліміт часу. Для скидання буфера використовуйте:
fflush(stdout) або cout.flush() в C++;
System.out.flush() в Java;
flush(output) в Pascal;
stdout.flush() в Python.
Коли ви визначили загадане число , виведіть «».
Після цього, якщо це був останній набір вхідних даних, ви повинні завершити роботу своєї програми. Інакше потрібно продовжити взаємодію з наступним набором вхідних даних.
— максимальна кількість запитів типу «?», яку може використати ваша програма в одному наборі вхідних даних. Виведення відповіді типу «!» не вважається запитом.
Зверніть увагу, що якщо ваш запит недійсний, інтерактор виведе «-1» та припинить роботу. Запит вважається недійсним, якщо:
не задовольняє обмеження 1 \le x \le 10^9;
кількість запитів у поточному наборі вхідних даних перевищила ;
відповідь «! n» неправильна.
Якщо ви зчитали «-1», негайно завершіть програму, щоб отримати вердикт Неправильна відповідь замість довільного вердикту.
Приклад 1
Розглянемо приклад. Нехай у цьому прикладі додатково відомо, що загадане число менше за .
Після запиту x = 1 та відповіді ми розуміємо, що перша цифра загадного числа дорівнює .
Після запиту x = 59 та відповіді ми розуміємо, що перша цифра добутку загаданого числа на дорівнює .
Серед усіх чисел менших за , які не діляться на , лише число задовольняє обидві ці умови. Тому відповідь у прикладі дорівнює .
( бали): n \le 10;
( балів): n \le 100;
( балів): n \le 1000;
( балів): n \le 10000;
( балів): є повним квадратом;
( балів): n \le 10^5;
( балів): n \le 10^6;
( балів): n \le 10^7;
( балів): n \le 5 \cdot 10^7;
( балів): без додаткових обмежень.
Розв'язок проходить підзадачу лише тоді, коли правильно знаходить число для кожного набору вхідних даних цієї підзадачі, використовуючи не більше ніж запитів у кожному наборі.