}
==

Este bine ştiut faptul că dacă *$p$* este sortat, atunci codul returnează *$true$* dacă şi numai dacă *$target$* apare în *$p$*. Pe de altă parte, acest lucru poate să nu se întâmple dacă *$p$* nu este sortat.

Este bine ştiut faptul că dacă *$p$* este sortat, atunci codul returnează true dacă şi numai dacă *$target$* apare în *$p$*. Pe de altă parte, acest lucru poate să nu se întâmple dacă *$p$* nu este sortat.

Vi se dă un număr natural $n$ şi o secvenţă $b{~1~},..., b{~n~} ∈ {*$true$*, *$false$*}$. Se garantează că există un număr natural $k$ pentru care $n = 2^k^ − 1$. Trebuie să generaţi o permutare $p$ a elementelor ${1, . . . , n}$ care îndeplineşte anumite condiţii. Fie $S(p)$ numărul de indici $i ∈ {1,..., n}$ pentru care *$binary_search(n, p, i)$* *nu* returnează $b{~i~}$. Trebuie sa alegeţi $p$ astfel încât $S(p)$ este mic (aşa cum este detaliat în secţiunea "Restricţii").

h2. Date de intrare

Fişierul de intrare $binsearch.in$ conţine pe prima linie $T$, numărul de teste. Urmează apoi testele.
 
Prima linie a unui test conţine numărul natural $n$. Pe cea de-a doua linie se găseşte un şir de $n$ caractere ce conţine doar caracterele $'0'$ şi $'1'$. Aceste caractere nu sunt separate prin spaţii. Dacă cel de-al $i$-lea caracter este $'1'$, atunci $b{~i~} = *true*$, iar dacă este $'0'$, atunci $b{~i~} = *false*$.

Fişierul de intrare $binsearch.in$ ...

h2. Date de ieşire