Skibidi Sətir

Giriş

Birinci sətirdə bir tam ədəd $T$ $(1 \leq T \leq 1 0^{4})$ (1 \le T \le 10^4) — test hallarının sayı verilir.

Hər test halının birinci sətrində bir tam ədəd $n$ $(3 \leq n \leq 2 \cdot 1 0^{5})$ (3 \le n \le 2 \cdot 10^5) — axtarılan sətrin uzunluğu verilir.

Hər test halının ikinci sətrində uzunluğu $n - 2$ n-2 olan ikilik $t$ sətri $(t_{i} \in {0, 1})$ (t_i \in \{\mathtt{0}, \mathtt{1}\}) verilir.

Bütün test halları üzrə $n$ qiymətlərinin cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i aşmadığına zəmanət verilir.

Hər test halı üçün şərtləri ödəyən, kiçik latın hərflərindən ibarət leksikoqrafik baxımdan ən kiçik $s$ sətrini çap edin.

Nümunə 1

Loading

Birinci test halı üçün $s = aabcba$ s = \mathtt{aabcba}:

$i = 1$ i = 1: $aab$ sətrinin $f = 5$ f = 5 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.
$i = 2$ i = 2: $abc$ sətrinin $f = 6$ f = 6 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 0$ f \bmod 2 = 0.
$i = 3$ i = 3: $bcb$ sətrinin $f = 5$ f = 5 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.
$i = 4$ i = 4: $cba$ sətrinin $f = 6$ f = 6 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 0$ f \bmod 2 = 0.

Beləliklə, alınan $t$ tələb olunduğu kimi $1010$ -a bərabərdir.

İkinci test halı üçün $s = abcbaa$ s = \mathtt{abcbaa}:

$i = 1$ i = 1: $abc$ sətrinin $f = 6$ f = 6 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 0$ f \bmod 2 = 0.
$i = 2$ i = 2: $bcb$ sətrinin $f = 5$ f = 5 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.
$i = 3$ i = 3: $cba$ sətrinin $f = 6$ f = 6 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 0$ f \bmod 2 = 0.
$i = 4$ i = 4: $baa$ sətrinin $f = 5$ f = 5 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.

Beləliklə, alınan $t$ tələb olunduğu kimi $0101$ -ə bərabərdir.

Üçüncü test halı üçün $s = aaabcaa$ s = \mathtt{aaabcaa}:

$i = 1$ i = 1: $aaa$ sətrinin $f = 3$ f = 3 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.
$i = 2$ i = 2: $aab$ sətrinin $f = 5$ f = 5 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.
$i = 3$ i = 3: $abc$ sətrinin $f = 6$ f = 6 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 0$ f \bmod 2 = 0.
$i = 4$ i = 4: $bca$ sətrinin $f = 6$ f = 6 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 0$ f \bmod 2 = 0.
$i = 5$ i = 5: $caa$ sətrinin $f = 5$ f = 5 müxtəlif boş olmayan altsətri var, deməli $f mod 2 = 1$ f \bmod 2 = 1.

Beləliklə, alınan $t$ tələb olunduğu kimi $11001$ -ə bərabərdir.

Altməsələ $1$ ( $25$ bal): $(t = 00000 \dots 0)$ (t=\mathtt{00000 \ldots 0})
Altməsələ $2$ ( $25$ bal): $(t = 11111 \dots 1)$ (t=\mathtt{11111\ldots 1})
Altməsələ $3$ ( $50$ bal): $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000)
Altməsələ $4$ ( $100$ bal): $(1 \leq \sum n \leq 1 0^{4})$ (1 \le \sum n \le 10^4)
Altməsələ $5$ ( $150$ bal): Əlavə məhdudiyyət yoxdur