A. Похожие строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Двоичная строка — это такая строка, каждый символ которой — либо 0, либо 1. Назовем две двоичные строки $$$a$$$ и $$$b$$$ одинаковой длины похожими, если хотя бы в одной позиции их символы совпадают (существует такое число $$$i$$$, что $$$a_i = b_i$$$). Например:

  • 10010 и 01111 похожи (у них один и тот же символ в позиции $$$4$$$);
  • 10010 и 11111 похожи;
  • 111 и 111 похожи;
  • 0110 и 1001 не являются похожими.

Вам дано целое число $$$n$$$ и двоичная строка $$$s$$$, состоящая из $$$2n-1$$$ символов. Обозначим за $$$s[l..r]$$$ непрерывную подстроку $$$s$$$, начиная с $$$l$$$-го символа и заканчивая $$$r$$$-м символом (иными словами, $$$s[l..r] = s_l s_{l + 1} s_{l + 2} \dots s_r$$$).

Постройте двоичную строку $$$w$$$ длины $$$n$$$, похожую на все строки из этого списка: $$$s[1..n]$$$, $$$s[2..n+1]$$$, $$$s[3..n+2]$$$, ..., $$$s[n..2n-1]$$$.

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

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

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

Вторая строка содержит двоичную строку $$$s$$$ длины $$$2n - 1$$$. Каждый символ $$$s_i$$$ — либо 0, либо 1.

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

Для каждого набора входных данных выведите удовлетворяющую условию двоичную строку $$$w$$$ длины $$$n$$$. Если существует несколько таких строк — выведите любую из них. Можно показать, что хотя бы одна такая строка $$$w$$$ всегда существует.

Пример
Входные данные
4
1
1
3
00000
4
1110000
2
101
Выходные данные
1
000
1010
00
Примечание

Объяснение примера из условия (совпадающие символы в одинаковых позициях выделены жирным):

Первый набор входных данных:

  • $$$\mathbf{1}$$$ похожа на $$$s[1..1] = \mathbf{1}$$$.

Второй набор входных данных:

  • $$$\mathbf{000}$$$ похожа на $$$s[1..3] = \mathbf{000}$$$;
  • $$$\mathbf{000}$$$ похожа на $$$s[2..4] = \mathbf{000}$$$;
  • $$$\mathbf{000}$$$ похожа на $$$s[3..5] = \mathbf{000}$$$.

Третий набор входных данных:

  • $$$\mathbf{1}0\mathbf{10}$$$ похожа на $$$s[1..4] = \mathbf{1}1\mathbf{10}$$$;
  • $$$\mathbf{1}01\mathbf{0}$$$ похожа на $$$s[2..5] = \mathbf{1}10\mathbf{0}$$$;
  • $$$\mathbf{10}1\mathbf{0}$$$ похожа на $$$s[3..6] = \mathbf{10}0\mathbf{0}$$$;
  • $$$1\mathbf{0}1\mathbf{0}$$$ похожа на $$$s[4..7] = 0\mathbf{0}0\mathbf{0}$$$.

Четвертый набор входных данных:

  • $$$0\mathbf{0}$$$ похожа на $$$s[1..2] = 1\mathbf{0}$$$;
  • $$$\mathbf{0}0$$$ похожа на $$$s[2..3] = \mathbf{0}1$$$.