길이가 $n$인 이진 문자열 $s$($01$ 문자열)가 주어집니다. 수식의 최종 값이 가능한 한 커지도록 $s[2 \ldots n - 1]$ 중 한 문자를 $\oplus$로 바꾸어야 합니다.

$\oplus$는 이진 XOR 연산을 나타냅니다. 치환 후 $\oplus$의 양쪽은 모두 이진수로 간주됩니다.

입력

하나의 테스트 케이스는 여러 개의 데이터 세트를 포함합니다.

입력의 첫째 줄은 데이터 세트의 개수 $T$ ($1 \le T \le 10^5$)로, 이 테스트 케이스에 포함된 데이터 세트의 수를 나타냅니다.

각 데이터 세트마다 이진 문자열 $s$ ($3 \le |s| \le 5 \cdot 10^5$)가 한 줄에 주어집니다.

하나의 테스트 케이스 안에서 $\sum |s| \le 5 \cdot 10^5$임이 보장됩니다.

출력

각 데이터 세트마다 가장 큰 결과를 이진 형태로 나타내는 이진 문자열을 한 줄에 출력합니다(단일 숫자 $0$인 경우를 제외하고 숫자 문자열은 선행하는 $0$을 포함할 수 없습니다).

예제

입력 1

5
010
0110
1000
10101
01000

출력 1

0
10
10
100
10