et-comes-to-india

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 K^th character in the N^th 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 K^th character of the sequence DN. If the K^th 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 K^th character of the sequence DN (or -1 if it doesn't exist) in a separate line.

Constraints
1 ≤ T ≤ 10^5
1 ≤ N ≤ 50
1 ≤ K ≤ 10^16

SAMPLE INPUT
4
1 1
2 1
2 3
2 5

SAMPLE OUTPUT
G
G
C
-1

Explanation

See example given above.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def sol(n,k):
	L = (2**n) - 1
	if k > L or k < 1 :
		return -1
	if k == L/2+1 :
		return 0
	if k < L/2+1 :
		return sol(n-1,k)
	else:
		return 1-sol(n-1,L+1-k)

#def sol(n,k):
#	L = (2**n) - 1 ;	
#	if  k > L :
#		return -1
#	f=0
#	while n>-1 :
#		if n==1:
#			if k==1: return f
#			else: return -1
#		if  k == L/2 + 1 :
#			return f
#		if  k > L/2 :
#			f=1-f
#			k = L+1-k 
#		n-=1
#		L>>=1
#	return 111

for t in range(eval(input())):
	n,k = list(map( int, input().split() ))
	ans = 0
	ans = sol(n,k)
	if ans == -1 : print('-1')
	if ans == 0 : print('G')
	if ans == 1 : print('C')


'''def sol(n,k):
	L = (2**n) - 1
	if k > L :
		return '-1'
	if k == L/2+1 :
		return 'G'
	if k < L/2+1 :
		return sol(n-1,k)
	else:
		ans = sol(n-1,L+1-k)
		if ans=='G':
			return 'C'
		else:
			return 'G'
'''

def sol(n,k):
	L = (2**n) - 1 ;	
	if  k > L :
		return -1
	f=0
	while n>-1 :
		if n==1:
			if k==1: return f
			else: return -1
		if  k == L/2 + 1 :
			return f
		if  k > L/2 :
			f=1-f
			k = L+1-k 
		n-=1
		L>>=1
	return 111

for t in range(eval(input())):
	n,k = list(map( int, input().split() ))
	ans = sol(n,k)
	if ans == -1 : print('-1')
	if ans == 0 : print('G')
	if ans == 1 : print('C')


def sol(n,k):
	L = (2**n) - 1
	if k > L or k < 1 :
		return -1
	if k == L/2+1 :
		return 0
	if k < L/2+1 :
		return sol(n-1,k)
	else:
		return 1-sol(n-1,L+1-k)

#def sol(n,k):
#	L = (2**n) - 1 ;	
#	if  k > L :
#		return -1
#	f=0
#	while n>-1 :
#		if n==1:
#			if k==1: return f
#			else: return -1
#		if  k == L/2 + 1 :
#			return f
#		if  k > L/2 :
#			f=1-f
#			k = L+1-k 
#		n-=1
#		L>>=1
#	return 111

for t in range(eval(input())):
	n,k = list(map( int, input().split() ))
	ans = sol(n,k)
	if ans == -1 : print('-1')
	if ans == 0 : print('G')
	if ans == 1 : print('C')


def sol(n,k):
	L = (2**n) - 1
	if k > L :
		return -1
	if k == L/2+1 :
		return 0
	if k < L/2+1 :
		return sol(n-1,k)
	else:
		return 1-sol(n-1,L+1-k)

#def sol(n,k):
#	L = (2**n) - 1 ;	
#	if  k > L :
#		return -1
#	f=0
#	while n>-1 :
#		if n==1:
#			if k==1: return f
#			else: return -1
#		if  k == L/2 + 1 :
#			return f
#		if  k > L/2 :
#			f=1-f
#			k = L+1-k 
#		n-=1
#		L>>=1
#	return 111

for t in range(eval(input())):
	n,k = list(map( int, input().split() ))
	ans = sol(n,k)
	if ans == -1 : print('-1')
	if ans == 0 : print('G')
	if ans == 1 : print('C')


def pf(k):
	h = k & -k
	k &= (h << 1)
	return (k==0)
for _ in range(int(input())):
	n, k = list(map(int, input().split()))
	if 2 ** n  - 1 < k:
		print(-1)
	else:
		print("G" if pf(k) else "C")
	


allens = [1,3,7,15]
for x in range(4, 51):
	allens.append(allens[x-1] * 2 + 1)


for _ in range(eval(input())):
	n, k = list(map(int, input().split()))
	if k > allens[n-1]:
		print("-1")
	else:
		while k%2 == 0:
			k /= 2
		if (k-3)%4 == 0:
			print("C")
		else:
			print("G")
	   


'''def sol(n,k):
	L = (2**n) - 1
	if k > L :
		return '-1'
	if k == L/2+1 :
		return 'G'
	if k < L/2+1 :
		return sol(n-1,k)
	else:
		ans = sol(n-1,L+1-k)
		if ans=='G':
			return 'C'
		else:
			return 'G'
'''

def sol(n,k):
	L = (2**n) - 1 ;	
	if  k > L :
		return -1
	f=0
	while n>-1 :
		if  k == L/2 + 1 :
			return f
		if  k > L/2 :
			f=1-f
			k = L+1-k 
		L>>=1
	return 111

for t in range(eval(input())):
	n,k = list(map( int, input().split() ))
	ans = sol(n,k)
	if ans == -1 : print('-1')
	if ans == 0 : print('G')
	if ans == 1 : print('C')


'''def sol(n,k):
	L = (2**n) - 1
	if k > L :
		return '-1'
	if k == L/2+1 :
		return 'G'
	if k < L/2+1 :
		return sol(n-1,k)
	else:
		ans = sol(n-1,L+1-k)
		if ans=='G':
			return 'C'
		else:
			return 'G'
'''

def sol(n,k):
	L = (2**n) - 1 ;	
	if  k > L :
		return -1
	f=0
	while n>-1 :
		if  k == L/2 + 1 :
			return f
		if  k > L/2 :
			f=1-f
			k = L+1-k 
		n-=1
		L>>=1
	return 111

for t in range(eval(input())):
	n,k = list(map( int, input().split() ))
	ans = sol(n,k)
	if ans == -1 : print('-1')
	if ans == 0 : print('G')
	if ans == 1 : print('C')