By XIV Maratona de Programação IME-USP, 2010 Brazil
Zé Coquinho is a crafstman that produces sculptures with coconuts. The dry coconuts are cut in half and the bowls formed by the shells are painted and used to build the sculptures. The sculptures are very famous, being sought by collectors worldwide.
Figure 1: The most famous coconut sculpture made by Zé Coquinho.
The sculptures of Zé Coquinho are sequences of bowls glued to each other. A well-formed sculpture is defined by the following set of rules;
Note that all the well-formed sculptures are built using only the above set of rules. Let T be a sculpture formed by coconuts' bowls. If T isn't a well-formed sculpture, we say that T is a malformed sculpture.
A striking feature of Ze Coquinho's sculptures is that they are never well-formed; all the sculptures that he did in his long live are malformed.
The Graviuna's Modern Art Museum wants to make a presentation of Ze Coquinho's sculptures. To organize the presentation, the museum decided to order the sculptures in lexicographical order. In the lexicographical order defined by the museum the symbol ( comes before the symbol ). For example, ((( < (() and )( < )).
The length of a malformed sculpture is the number of bowls that it possess.
Given two integers N and K, you must determine the K-th malformed sculpture of length N considering the order defined by the museum. Consider that Ze Coquinho made all the malformed sculptures of length N.
The input consists of several instances. The first line has a integer T that indicates the number of instances.
The first (and only) line of each instance has two integers N and K, where 1 ≤ N ≤ 50 e 1 ≤ K ≤ 2n − 1, indicating respectively the length of the sculpture and the index of the sculpture (in the lexicographical order) that you must determine.
For each instance print a line containing the K-th malformed sculpture of length N. If such sculpture doesn't exist print a line containing -1.
|Sample Input||Sample Output|