SPOJ Brasil

Zé Coquinho é um artesão que produz esculturas feitas com cocos. Os cocos secos são cortados ao meio e as cuias formadas pelas cascas são pintadas e utilizadas para construir as esculturas. As esculturas são muito famosas, sendo procuradas por colecionadores de todo o mundo.

Figura 1: A mais famosa escultura de coco feita por Zé Coquinho.

As esculturas de Zé Coquinho são sequências de cuias coladas umas nas outras. Uma escultura bem-formada é definida pelo seguinte conjunto de regras:

• uma sequência vazia de cuias é uma escultura bem-formada.
• se T é um escultura bem-formada, então uma escultura formada por (T) (ou seja uma cuia aberta para a direita, seguida de T, seguida de uma cuia aberta para a esquerda) é uma escultura bem-formada;
• se T e S são esculturas bem-formadas, então ST (ou seja, a escultura S seguida de T) é uma escultura bem-formada.

Note que todas as esculturas bem-formadas são construídas usando apenas as regras descritas acima. Seja T uma escultura formada por cuias de coco. Se T não é uma escultura bem-formada, dizemos que T é uma escultura mal-formada.
Uma característica marcante das esculturas de Zé Coquinho é que elas nunca são bem-formadas; todas as esculturas que ele fez na sua longa vida são mal-formadas.
O Museu de Arte Moderna de Graviúna quer fazer uma exposição de esculturas de Zé Coquinho. Para organizar a exposição, o museu resolveu ordenar as esculturas em ordem lexicográfica. Na ordem lexicográfica definida pelo museu o símbolo ( vem antes do que o símbolo ). Por exemplo, ( ( ( < ( ( ) e ) ( < ) ).
O comprimento de uma escultura mal-formada é o número de cuias que a mesma possui. Dados dois inteiros N e K, você deve determinar a K-ésima escultura mal-formada de comprimento N considerando a ordem definida pelo museu. Considere que Zé Coquinho fez todas as esculturas mal-formadas de comprimento N.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira (e única) linha de cada instância contém dois inteiros N e K, onde 1 ≤ N ≤ 50 e 0 ≤ K ≤ 2^N-1, indicando respectivamente o comprimento da escultura e o índice da escultura (na ordem lexicográfica) que você deve determinar.

Saída

Para cada instância imprima uma linha contendo a K-ésima escultura mal-formada de comprimento N. Caso não exista uma tal escultura imprima uma linha contendo -1.

Exemplo

Entrada:
4
4 0
4 4
6 63
7 13

Saída:
((((
())(
-1
((())()