E.T. comes to India

3.5

8 votes
Problem

An extraterrestrial visit!

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.


Input Format

The first line contains T, then number of test cases.

T lines follow, each contains a value of N and K.

Output Format

For each test case, print the Kth character of the sequence DN (or -1 if it doesn't exist) in a separate line.

Constraints

1 <= T<= 105
1 <= N <= 50
1 <= K <= 1016

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

See example given above.

Editor Image

?