Skibidi String

Вхідні дані

Перший рядок містить одне ціле число $T$ $(1 \leq T \leq 1 0^{4})$ (1 \le T \le 10^4) — кількість наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить ціле число $n$ $(3 \leq n \leq 2 \cdot 1 0^{5})$ (3 \le n \le 2 \cdot 10^5) — довжину потрібного рядка.

Другий рядок кожного набору вхідних даних містить бінарний рядок $t$ довжини $n - 2$ n-2 $(t_{i} \in {0, 1})$ (t_i \in \{\mathtt{0}, \mathtt{1}\}).

Гарантується, що сума $n$ по всіх наборах вхідних даних не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть лексикографічно найменший рядок $s$ , що складається з малих латинських літер і задовольняє умови.

Приклади

Приклад 1

Loading

Примітка

Для першого набору вхідних даних $s = aabcba$ s = \mathtt{aabcba}:

$i = 1$ i = 1: $aab$ має $f = 5$ f = 5 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.
$i = 2$ i = 2: $abc$ має $f = 6$ f = 6 різних непорожніх підрядків, тому $f mod 2 = 0$ f \bmod 2 = 0.
$i = 3$ i = 3: $bcb$ має $f = 5$ f = 5 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.
$i = 4$ i = 4: $cba$ має $f = 6$ f = 6 різних непорожніх підрядків, тому $f mod 2 = 0$ f \bmod 2 = 0.

Отже, отриманий $t$ дорівнює $1010$ , як і потрібно.

Для другого набору вхідних даних $s = abcbaa$ s = \mathtt{abcbaa}:

$i = 1$ i = 1: $abc$ має $f = 6$ f = 6 різних непорожніх підрядків, тому $f mod 2 = 0$ f \bmod 2 = 0.
$i = 2$ i = 2: $bcb$ має $f = 5$ f = 5 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.
$i = 3$ i = 3: $cba$ має $f = 6$ f = 6 різних непорожніх підрядків, тому $f mod 2 = 0$ f \bmod 2 = 0.
$i = 4$ i = 4: $baa$ має $f = 5$ f = 5 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.

Отже, отриманий $t$ дорівнює $0101$ , як і потрібно.

Для третього набору вхідних даних $s = aaabcaa$ s = \mathtt{aaabcaa}:

$i = 1$ i = 1: $aaa$ має $f = 3$ f = 3 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.
$i = 2$ i = 2: $aab$ має $f = 5$ f = 5 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.
$i = 3$ i = 3: $abc$ має $f = 6$ f = 6 різних непорожніх підрядків, тому $f mod 2 = 0$ f \bmod 2 = 0.
$i = 4$ i = 4: $bca$ має $f = 6$ f = 6 різних непорожніх підрядків, тому $f mod 2 = 0$ f \bmod 2 = 0.
$i = 5$ i = 5: $caa$ має $f = 5$ f = 5 різних непорожніх підрядків, тому $f mod 2 = 1$ f \bmod 2 = 1.

Отже, отриманий $t$ дорівнює $11001$ , як і потрібно.

Оцінювання

Підзадача $1$ ( $25$ балів): $(t = 00000 \dots 0)$ (t=\mathtt{00000 \ldots 0})
Підзадача $2$ ( $25$ балів): $(t = 11111 \dots 1)$ (t=\mathtt{11111\ldots 1})
Підзадача $3$ ( $50$ балів): $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000)
Підзадача $4$ ( $100$ балів): $(1 \leq \sum n \leq 1 0^{4})$ (1 \le \sum n \le 10^4)
Підзадача $5$ ( $150$ балів): Без додаткових обмежень