Un número binario en juego otra vez. Pero no igual, lee atentamente esta definición. Si tu quieres incrementar un número en 1, intenta incrementar el último dígito de su representación binaria. Si no se puede. Asigna 0 al último dígito, e intenta incrementar el dígito que esta antes de el, y así sucesivamente hasta que logres incrementar un dígito.

Por ejemplo, la secuencia decimal:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Convertido a binario:

1, 10, 11, 100, 101, 110, 111, 1110, 1001, 1010, 1011, …

Dado un String C que contiene la representación binaria de un entero positivo X. Retorna un String conteniendo la representación binaria de (X+1). Ten en cuenta que el resultado no debe tener ceros adelante.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 <= M <= 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

C : Una cadena de longitud entre 1 y 30 inclusive, que será la representación binaria de un número entero.

Cada carácter de la cadena C será 1 o 0.
El primer carácter de la cadena siempre será 1

Output

Para cada caso deberás imprimir la representación (X+1) en binario.

Entrada de ejemplo