#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/16/problems/b

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Smallest Mex String - Repovive Premier Round 6 | Repovive | 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

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

16B. Smallest Mex String

Constraints

Input

Output

Samples

16B. Smallest Mex String

Constraints

Input

Output

Samples