**Crazy Subsequences solution codechef** – Chef has a binary string $S$. He can modify it by choosing any subsequence of length $3$ from it and deleting the **first** and **last** character of the subsequence.

Table of Contents

## [Solution] Crazy Subsequences solution codechef

For example, if $S=110101$, Chef can choose the subsequence marked in red and delete its first and last characters, obtaining the string $S=1011$.

Chef wonders what is the lexicographically largest string he can obtain by modifying the original string using a finite number of operations. Please help Chef in this task.

**Note:** A binary string $A$ is said to be lexicographically larger than another binary string $B$ if:

- $B$ is a proper prefix of $A$ (for example, $101$ is lexicographically larger than $10$); or
- There exists an index $i$ such that $A_{1}=B_{1},A_{2}=B_{2},…,A_{i−}=B_{i−}$ and $A_{i}>B_{i}$.

### Input Format

- The first line of input will contain a single integer $T$, denoting the number of test cases.
- Each test case consists of a single line of input containing the original binary string $S$.

### Output Format

For each test case, output on a new line the lexicographically largest string Chef can obtain.

## Crazy Subsequences solution codechef

- $1≤T≤2⋅1_{4}$
- $3≤∣S∣≤1_{5}$
- $S$ is a binary string, i.e, only contains the characters $0$ and $1$ in it
- The sum of $∣S∣$ over all test cases won’t exceed $3⋅1_{5}$.

### Sample 1:

4 101 1010 0000 0001

101 11 0000 01

## Crazy Subsequences solution codechef Explanation:

**Test case $1$:** It is optimal to not perform any moves.

**Test case $2$:** In one move, by choosing the subsequence $1010$, the string can be made into $11$, which is the lexicographically largest possible.

**Test case $3$:** It is optimal to not perform any move.