C. Взлом пароля
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Димаш узнал, что Мансур написал про него что-то очень нехорошее своему знакомому, поэтому он решил во что бы ни стало узнать его пароль и узнать, что же именно он написал.

Поверив в силу своего пароля, Мансур сообщил, что его пароль — это бинарная строка размера $$$n$$$. А также он готов отвечать на вопросы Димаша следующего вида:

Димаш говорит бинарную строку $$$t$$$, и Мансур отвечает, правда ли, что $$$t$$$ является подстрокой его пароля.

Помогите Димашу узнать пароль не более чем за $$$2n$$$ операций, иначе Мансур поймет подвох и перестанет с ним общаться.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Протокол взаимодействия

В начале каждого набора входных данных вначале прочитайте $$$n$$$ ($$$1 \le n \le 100$$$) — размер бинарной строки. Затем приступайте к ее угадыванию.

Для угадывания каждой строки $$$s$$$ вы можете сделать не более $$$2n$$$ запросов следующего вида:

  • «? t», где $$$t$$$ — бинарная строка, где ($$$1 \le |t| \le n$$$).

В ответ на этот запрос вы получите $$$1$$$, если $$$t$$$ является подстрокой $$$s$$$, и $$$0$$$ в противном случае.

Когда вы узнаете ответ, выведите одну строку следующего формата:

  • «! s», где $$$s$$$ — бинарная строка размера $$$n$$$.

После этого переходите к решению следующего набора входных данных.

Если вы сделаете некорректную попытку или превысите лимит в $$$2n$$$ попыток, вы считаете $$$-1$$$ вместо ответа и получите вердикт Неправильный ответ. В таком случае ваша программа должна немедленно завершиться, чтобы избежать неопределенных вердиктов.

После вывода запросов не забудьте выводить символ перевода строки и сбрасывать буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы:

Для взломов используйте следующий формат:

Первая строка должна содержать одно целое число $$$t$$$ ($$$1\le t\le 100$$$) — количество наборов входных данных.

Первая строка каждого набора должна содержать одно число $$$n$$$ ($$$1 \le n \le 100$$$) — длину строки. А вторая строка должна содержать бинарную строку размера $$$n$$$.

Пример
Входные данные
4
3

0

0

1

4

4

2
Выходные данные


? 00

? 000

? 010

! 010

! 1100

! 0110

! 10
Примечание

В первом примере задана строка $$$010$$$. Поэтому ответы на запросы следующие:

«? 00» $$$00$$$ не является подстрокой $$$010$$$, поэтому ответ $$$0$$$.

«? 000» $$$000$$$ не является подстрокой, поэтому ответ $$$0$$$.

«? 010» $$$010$$$ является подстрокой, поэтому ответ $$$1$$$.

Во втором примере задана строка $$$1100$$$, в третьем $$$0110$$$, а в четвертом $$$10$$$.