Waliqui, es el nombre de una inteligencia artificial que estamos probando para la rotación de un número N (10 ≤ N < 1000000), en base a su equivalente número binario. Tomando su equivalente binario, el número 1 indica recorrer a la izquierda y el número 0 indica recorrer a la derecha.

Por ejemplo, si N = 13, su equivalente binario será: 1101. Lo que hará Waliqui es rotar el número 13 primero a la izquierda (31), luego otra vez a la izquierda (13), luego a la derecha (31) y finalmente a la izquierda (13), entregando el resultado final: 13.

Tomemos otro ejemplo, si N=1325, su equivalente binario será: 10100101101

El valor a imprimir será: 3251

Se tiene un entero K (1 ≤ K ≤ 100) que indica el número de casos, cada línea contiene un número N (1 ≤ N ≤ 100000).

Imprime en una línea individual el resultado por cada entrada, que representa el número obtenido después de aplicar todas las rotaciones a la izquierda o derecha, según corresponda.