Відгадай число#527

Відгадай число

1 секунда
256 мегабайтів
Дуже складна

Загадано ціле число (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

Loading
Loading

Примітка

Розглянемо приклад. Нехай у цьому прикладі додатково відомо, що загадане число менше за .

Після запиту x = 1 та відповіді ми розуміємо, що перша цифра загадного числа дорівнює .

Після запиту x = 59 та відповіді ми розуміємо, що перша цифра добутку загаданого числа на дорівнює .

Серед усіх чисел менших за , які не діляться на , лише число задовольняє обидві ці умови. Тому відповідь у прикладі дорівнює .

Оцінювання

  1. ( бали): n \le 10;

  2. ( балів): n \le 100;

  3. ( балів): n \le 1000;

  4. ( балів): n \le 10000;

  5. ( балів): є повним квадратом;

  6. ( балів): n \le 10^5;

  7. ( балів): n \le 10^6;

  8. ( балів): n \le 10^7;

  9. ( балів): n \le 5 \cdot 10^7;

  10. ( балів): без додаткових обмежень.

Розв'язок проходить підзадачу лише тоді, коли правильно знаходить число для кожного набору вхідних даних цієї підзадачі, використовуючи не більше ніж запитів у кожному наборі.