its-all-about-magic

Recently Oz has found a magical string consisting of single digit "1". After experimenting on the string, Oz found a weird magical property of the string that is  whenever he touches the string then each digit "1" of string changed to digit "0" and each digit "0" of string changed to "01". Oz found this property interesting and immediately asked a question to RK : "How many 1's and 0's will be in the magical string if he touches the string M times ?"

Input :

The first line contains the number of test cases T . Each test case consists of a positive integer - M . 

Output :

For each test case output two space-separated integers, number of 1's and number of 0's in the magical string if Oz touches the string M times.

Constraints :

1 ≤ T ≤20

1 ≤ M ≤90

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
0 1
1 1

Source: hackerearth | Difficulty: EASY
Tags: Fundamentals

Ad-hoc


Solutions:
t = eval(input())
l=[[1,0]]
o=[]
for i in range(0,t):
	n = eval(input())
	if n >= len(l):
		for j in  range(len(l),n+1):
			zero = l[len(l)-1][0]+l[len(l)-1][1]
			one  = l[len(l)-1][1]
			l.append([one,zero])
	o.append(l[n])

for i in o:
	s = str(i[0])+" "+str(i[1])
	print(s)		



t = int(eval(input()))
for i in range(0,t):
	p = 0
	q = 1
	m = int(eval(input()))
	for j in range(1,m+1):
		temp = p
		p = p + q
		q = temp
	print(q, end=' ')
	print(p, end=' ')
	print() 


l=[[1,0]]
for i in range(90):
	temp=l[-1]
	a=temp[1]
	b=temp[0]+temp[1]
	temp=[a,b]
	l.append(temp)

t=int(input())
while t:
	t-=1
	m=int(input())
	print(l[m][0],l[m][1])


t = eval(input())
for i in range(t):
	n=eval(input())
	a=1
	b=0
	for j in range(n):
		temp=b
		b=a+b
		a=temp
	print(a,b)
	


t=eval(input())
for i in range(0,t):
	x=eval(input())
	a=0
	b=1
	c=1
	for i in range(1,x):
		c=a+b
		a=b
		b=c
	print((a), end=' ')
	print(b)


t=eval(input())

while(t>0):
	m=eval(input())
	if m<2:
		print("0 1")
	else:
		a0=1
		b0=1
		a1=0
		b1=1
		for i in range(m-2):
			
			temp0=b0+a0
			temp1=a1+b1
			a0=b0
			b0=temp0
			a1=b1
			b1=temp1
		print(b1,b0)
	t=t-1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
inp = input()
for i in range(int(inp)):
	num=input()
	a=1
	b=0
	for j in range(int(num)):
	    temp=b
	    b=a+b
	    a=temp
	print(a, end=' ')
	print(b)


n = eval(input())

while n:
	n -= 1
	p, q, m = 0, 1, eval(input())-1
	while m:
		m -= 1
		p, q = q, p+q
	print(p, q)
		


t = eval(input())
 
for i in range(0, t):
	m = eval(input())
	noOf0 = 1
	noOf1 = 0
	
	if m == 1:
		print(0,1)
	else:
		for j in range(1,m):
			prevNoOf1 = noOf1
			prevNoOf0 = noOf0
			noOf0 = noOf0 + prevNoOf1
			noOf1 = prevNoOf0
		print(noOf1,noOf0)


testcases = int(input())

for i in range(0, testcases):
	n = int(input())
	numberof0 = 1
	numberof1 = 0
	
	if n == 1:
		print(0,1)
	else:
		for j in range(1,n):
			previousnumberof1 = numberof1
			previousnumberof0 = numberof0
			numberof0 = numberof0 + previousnumberof1
			numberof1 = previousnumberof0
		print(numberof1,numberof0)


t=int(input())
for i in range(t):
	p=int(input())
	one=1
	zero=0
	for j in range(p):
		temp=zero
		zero=one+zero
		one=temp
	print(one,zero);


def process(k):
	a=1
	b=0
	for j in range(k):
		temp=b
		b=a+b
		a=temp
	print(a,b)
if __name__ == "__main__":
	t=int(input())
	while t>0:
		n=int(input())
		process(n)
		t-=1



one=[0 for i in range(91)]
zero=[0 for i in range(91)]
one[1]=0
zero[1]=1
for i in range(2,91):
	zero[i]=zero[i-1]+one[i-1]
	one[i]=zero[i-1]

t=int(input())
for ii in range(t):
	m=int(input())
	print(one[m], zero[m])


def count_1_0(c,c1,c0):
	if c == 1: return c1,c0
	else: return count_1_0(c-1,c0,c1+c0)

num = int(input())
for i in range(num):
	n = int(input())
	x,y = count_1_0(n,0,1)
	print(x,y)
	


tests=eval(input())
i=0
a=[0 for i in range(100)]
b=[0 for i in range(100)]
a[0]=0
a[1]=1
b[0]=1
b[1]=0
i=2
while(i<100):
	a[i]=a[i-1]+a[i-2]
	b[i]=b[i-1]+b[i-2]
	i=i+1
while(tests>0):
	n=eval(input())
	print(b[n], end=' ')
	print(a[n])
	tests=tests-1


l = []

for x in range(int(input())):
	l.append(int(input()))
	
def after_touchs(n):
	#for x in range(n):
	#	string = string.replace('1', '2').replace('0', '01').replace('2', '0')
		
	#return map(str, [string.count('1'), string.count('0')])
	
	zeros = 0
	ones = 1
	
	for x in range(n):
		zeros, ones = ones + zeros, zeros
		
	return tuple(map(str, (ones, zeros)))
	
for num in l:
	print(' '.join(after_touchs(num)))


test=eval(input())
for i in range(test):
	m=eval(input())
	if m>2:
		no_ones=1
		no_zeros=1
		for k in range(m-2):
			total=no_ones+no_zeros
			no_ones=no_zeros
			no_zeros=total
		print(no_ones,no_zeros)
	else:
		if m==1:
			print(0,1)
		else:
			print(1,1)


t = int(eval(input()))
for i in range(0,t):
	p = 0
	q = 1
	m = int(eval(input()))
	for j in range(1,m+1):
		temp = p
		p = p + q
		q = temp
	print(q, end=' ')
	print(p, end=' ')
	print()