Smallest Mex String - Repovive Premier Round 6 | Repovive

16B. Smallest Mex String

1000 pts1s256 MB

You are given a binary string $s$ .

You have to split $s$ into one or more non-empty contiguous substrings. Each character of $s$ must belong to exactly one substring.

For a binary string $x$ , define $mex(x)$ as the smallest non-negative integer that does not appear in $x$ as a digit. For example, $mex(\texttt{1})=0$ , $mex(\texttt{0})=1$ , and $mex(\texttt{01})=2$ .

After choosing a split, write the values of $mex$ of the substrings from left to right, without spaces. This gives a string of digits.

Find the lexicographically smallest string that can be obtained.

We use the usual definition of lexicographic order: if one string is a proper prefix of the other, the shorter string is smaller.

Constraints

$1 \le t \le 10^4$
$1 \le |s| \le 2 \times 10^5$
The sum of $|s|$ over all test cases is at most $2 \times 10^5$
Each character of $s$ is either $\texttt{0}$ or $\texttt{1}$

Input

t

\left. \begin{array}{l} s \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Taking the whole string as one segment gives mex 0.

Case 2

Taking the whole string as one segment gives mex 1.

Case 3

One valid partition is 0 | 1. The mex values are 1 and 0, so the resulting string is 10.

Output

Case 1

Case 2

Case 3

You are given a binary string $s$ .

You have to split $s$ into one or more non-empty contiguous substrings. Each character of $s$ must belong to exactly one substring.

After choosing a split, write the values of $mex$ of the substrings from left to right, without spaces. This gives a string of digits.

Find the lexicographically smallest string that can be obtained.

We use the usual definition of lexicographic order: if one string is a proper prefix of the other, the shorter string is smaller.

$1 \le t \le 10^4$
$1 \le |s| \le 2 \times 10^5$
The sum of $|s|$ over all test cases is at most $2 \times 10^5$
Each character of $s$ is either $\texttt{0}$ or $\texttt{1}$

t

\left. \begin{array}{l} s \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16B. Smallest Mex String

Constraints

Input

Output

Samples

16B. Smallest Mex String

Constraints

Input

Output

Samples