Remember your childhood friend JAADU from outer space?? Well, he is back again to our mighty Planet Earth.
But do you expect us geeks to introduce a character like Rohit Mehra in this story?
A Hell No!!
Instead, he encounters the creepy Scientists of Planet Earth all the way from S.H.I.E.L.D led by the great Scientist Dr. Jackal (Yee Haw). Dr. Jackal and his team capture JAADU and decide to carry out tests on him to study his biological structure (It’s not every day you get to slice open a real alien). To achieve this, scientists will have to study his genes which are organized in an infinitely long sequence of DNA strands in the body. DNA strands in his body are found to be encodings of the proteins G & C. Now they want to identify the gene core which is basically the Kth character in the Nth DNA strand.
You being a programmer are asked to devise a method to identify the gene core starting from the entry gene strand. Scientists have identified the pattern in which gene strands are organized:
D1 = "G"
D2 = "GGC"
D3 = "GGCGGCC"
. . .
DN = D(N-1) + "G" + switch(reverse(D(N-1))).
Where
switch operation converts any G’s in the sequence to C’s and vice versa
and
reverse operation reverses the sequence.
Eg:
Switch(GGC) = CCG
Reverse(GGC) = CGG
You are asked to figure out the Kth character of the sequence DN. If the Kth character doesn't exist in the sequence DN, output -1.
The first line contains T, then number of test cases.
T lines follow, each contains a value of N and K.
For each test case, print the Kth character of the sequence DN (or -1 if it doesn't exist) in a separate line.
1 <= T<= 105
1 <= N <= 50
1 <= K <= 1016
See example given above.