SP5015 CASTANET - Decode the Castanets

The contest just finished and you head out to show all the balloons you won to your coach who’s amazed! Contest organizers know that coders can get really excited during the five hours of contest, so they planned to take you to a flamenco performance in order to relax you a bit before the awards ceremony starts. Flamenco is indeed a traditional Spanish musical genre. The music itself is complex, and the footwork is lightning fast and must be executed with extraordinary precision. In addition the dancer may have to dance while using props such as castanets, shawls and fans.  The performer of this afternoon will be none other than Don Quijote de la Mancha! Unfortunately Don Quijote cannot find the scope for the castanets, nor does he remember it by heart. But he has always an encoded version of that scope with him, so that he can have a quick look at it just before the performance. As time is short, he needs your help to decode the encrypted version of the scope. The scope can be represented as a binary string b1..bN of N digits. ‘1’ stands for clap the castanet, ‘0’ means leave it quiet. Now the encryption was as follows:  Given the original scope, the below matrix is formed from the rotated versions of the string. Then the rows of the matrix are sorted in alphabetical order (‘0’ < ‘1’). The last column of this matrix, read from top to bottom, is the encrypted version of the scope Don Quijote is giving you. Your task would be to find the Fth line of the matrix, which is the original version of the castanet scope.

The input consists of no more than T (T

For each test case, output the scope for the castanets.