Rakesh has built a model rocket and wants to test how stable it is. He usually uses a magic box which runs some tests on the rocket and tells if it is stable or not, but his friend broke it by trying to find out how stable he is (very delicate magic indeed). The box only gives a polynomial equation now which can help Rakesh find the stability (a failsafe by the manufacturers). 

Rakesh reads the manual for the magic box and understands that in order to determine stability, he needs to take every other term and put them in two rows. Eg. If the polynomial is:
10 x^4 + 12 x^3 + 4 x^2 + 5 x + 3, the first two rows will be: 

Row 1: 10       4       3

Row 2: 12       5       0

For all other rows, the nth element of the rth row is found recursively by multiplying the 1st element of the (r-1)th row and (n+1)th element of the (r-2)th row and subtracting it with 1st element of the (r-2)th row multiplied by (n+1)th element of the (r-1)th row.

So Row 3 will be (12 * 4 - 10 * 5)   (12 * 3 - 10 * 0)

Row 3: -2           36      0

Row 4: -442        0       0

Row 5: -15912    0       0

There will not be any row six (number of rows = maximum power of x + 1)

The rocket is stable if there are no sign changes in the first column. 

If all the elements of the rth row are 0, replace the nth element of the rth row by the nth element of the (r-1)th row multiplied by (maximum power of x + 4 - r - 2n).

If the first element of any row is 0 and some of the other elements are non zero, the rocket is unstable.

Can you help Rakesh check if his rocket is stable?

Input Format:

1. First row with number of test cases (T).

2. Next T rows with the coefficients of the polynomials for each case (10 12 4 5 3 for the case above).

Output Format:

1. "1" if stable (without "")

2. "0" if unstable (without "")

Sample Input: 

1

10 12 4 5 3

Sample Output:

0

Difficulty: interview

Starter code:

Solutions:
import random

def sign(i):
    if i>0:
        return 1
    elif i<=0:
        return 0
bleh = []
for _ in range(int(input())):
    p = list(map(int,input().rstrip().split()))
    max_rows = len(p)
    if all([x==0 for x in p]):
        print(1)
        continue
    if max_rows <= 1:
        bleh.append(max_rows)
        continue
    max_pow = max_rows-1
    if len(p)%2 !=0 and len(p)>0:
        p.append(0)
    max_col = len(p)//2
    
    rows = [[0 for _ in range(max_col)] for _ in range(max_rows)]
    rows[0] = p[::2]
    rows[1] = p[1::2]
    if sign(rows[0][0]) != sign(rows[1][0]):
        print(0)
        continue
    
    for r in range(2,max_rows):
        for n in range(max_col-1):
                rows[r][n] = rows[r-1][0]*rows[r-2][n+1]-rows[r-2][0]*rows[r-1][n+1]
    
    last = sign(rows[0][0])
    flag = 1
    for i in range(1,len(rows)):
        curr = sign(rows[i][0])
        if rows[r] == [0 for _ in range(max_col)]:
            for n in range(max_col):
                rows[r][n] = rows[r-1][n]*(max_pow+4-(r+1)-2*(n+1)) 
        
        elif rows[i][0] == 0:
            if any([x != 0 for x in rows[i]]):
                flag = 0
                break
            else:
                curr = last
        if curr != last:
            flag = 0
            break
        last = curr    
    print(flag)


def solve():
    c = list(map(int, input().strip().split()))
    n = len(c)
    if n <= 2:
        print(1)
        return
    k = (n + 1) // 2
    r = [[], []]
    for i in range(n):
        if i % 2 == 0:
            r[0].append(c[i])
        else:
            r[1].append(c[i])
    if len(r[1]) < k:
        r[1].append(0)
    r[0].append(0)
    r[1].append(0)
    while k > 0:
        p = []
        for i in range(1, k + 1):
            p.append(r[-1][0] * r[-2][i] - r[-1][i] * r[-2][0])
        r.append(p + [0])
        k -= 1
    r = [x[0] for x in r]
    atleastz, allz = 0, 1
    for x in r:
        if x == 0:
            atleastz = 1
        else:
            allz = 0
    if atleastz:
        if allz:
            print(1)
        else:
            print(0)
        return
    for i in range(1, len(r)):
        if r[i] * r[i - 1] < 0:
            print(0)
            return
    print(1)

def main():
    t = int(input().strip())
    for _ in range(t):
        solve()

def __starting_point():
    main()
__starting_point()

# cook your dish here
def fun(st,en,l):
    for i in range(st,maxpow+1):
        for j in range(0,m-1):
            l[i][j]=l[i-1][0]*l[i-2][j+1]-l[i-2][0]*l[i-1][j+1]
            
for _ in range(int(input())):
    l=list(map(int,input().split()))
    n=len(l)
    el=[]
    ol=[]
    for i in range(n):
        if i%2==0:
            el.append(l[i])
        else:
            ol.append(l[i])
    if n%2!=0:
        ol.append(0)
    l=[]
    l.append(el)
    l.append(ol)
    m=len(el)
    maxpow=n-1
    for i in range(2,maxpow+1):
        l.append([0]*m)
    fun(2,maxpow+1,l)
    for i in range(maxpow+1):
        cze=0
        for j in range(m):
            if l[i][j]==0:
                cze+=1
        if cze == m:
            for k in range(m):
                l[i][k]=l[i-1][k]*maxpow+4-(i+1)-2*(k+1)
            fun(i+1,maxpow+1,l)
    check=0
    for i in range(maxpow+1):
        if l[i][0]==0 and sum(l[i][1:])!=0:
            print(0)
            check=1
            break
    if check==0:
        if l[0][0]>0:
            signchange=1
        else:
            signchange= -1
        c=0
        for i in range(maxpow+1):
            if l[i][0]>0:
                temp=1
            else:
                temp=-1
            if temp!=signchange:
                print(0)
                c=1
                break
        if c==0:
            print(1)
                
                


def SR(coeff):
    size = len(coeff) # Please work out what if n is small no, like 1 or 2
    #print("No. of rows will form is", size)
    max_power = size - 1
    Arr = [] # 2x2
    row1 = coeff[0::2]
    row2 = coeff[1::2]
    #print('row1: ', row1, '\n', 'row2: ', row2)
    ln = len(row1) #don't change this value
    if size%2 != 0: # if n is odd
        row2.append(0) # to balance row1 and row2
    # add 1 empty element in each row for safety
    row1.append(0) 
    row2.append(0) 
    Arr.append(row1)
    Arr.append(row2)
    #print('start')
    
    sign = lambda x: 1 if x > 0 else -1  
    s = [sign(row1[0]), sign(row2[0])] # keep track of sign of 1st member of each row
    
    for r in range(2,size):
        Arr.append([0]*(ln+1)) # create a row of empty elements
        #print(r+1,'th row created', Arr)
        
        for n in range(ln): #generate value of nth element of rth row
            #print(n+1, 'th element to fill')
            # below mean, (12 * 4) - (10*5)
            Arr[r][n] = (Arr[r-1][0] * Arr[r-2][n+1]) - (Arr[r-2][0] * Arr[r-1][n+1])
            
        
        s.append(sign(Arr[r][0]))
        #print("  Array Print:  ")
        #for k in Arr: print(k) 
        
    ''' If all the element of that row is zero case
    then nth element = nth element of its previous row *
    ((max. power of x) - 4 - r - 2n ) '''
    for i in range(len(Arr)): # i th row in Arr
        if list(set(Arr[i])) == [0]:       
            #print(Arr[i])
            for n in range(len(Arr[i])):
                # I think that make sense
                Arr[i][n] = (Arr[i-1][n] * (max_power + 4 - (i+1) - (2*(n+1))))
                
        elif Arr[i][0] == 0:
            return 0 
        
    ''' check if sign change '''
    if len(set(s)) == 1: # no sign change
        return 1
    else: # sign change
        return 0

            
          
T = int(input())
#coeff = [10, 12, 4, 5, 3, 2]
for t in range(T):
    coeff = [int(x) for x in input().split()] # [10, 12, 4, 5, 3]
    print(SR(coeff))

import numpy as np

t = int(input())
arr = []
for i in range(t):
	inp = input()
	arr.append(list(map(int, inp.split(" "))))
# print(arr)

def gen_array(arr1,arr2,mp,rn):
	arrg = [];
	if len(arr1)!=len(arr2):
		arr1.append(0)
	for j in range(len(arr2)-1):
		arrg.append(arr1[0]*arr2[j+1]-arr2[0]*arr1[j+1])
	ctz = not np.any(arrg)
	if ctz == True:
		for j in range(len(arrg)):
			arrg[j] = (mp+4-rn-2*(j+1))*arr1[j]
	return(arrg)

def check(rht):
	for i in range(len(rht)-1):
		if(rht[i][0]*rht[i+1][0]<=0):
			print(0)
			break
	else:
		print(1)

rh=[]
for i in range(t):
	rh.append([])
	arr1 =[]
	arr2 =[]
	for j in range(len(arr[i])-1,-1,-1):
		if j%2 == 0:
			arr1.append(arr[i][j])
		else:
			arr2.append(arr[i][j])
	arr1.reverse()
	arr2.reverse()
	# print(arr1)
	# print(arr2)
	rh[i].append(arr1)
	rh[i].append(arr2)
	for j in range(2,len(arr[i])):
		rh[i].append(gen_array(rh[i][j-1],rh[i][j-2],arr[i][0],j+1))
	check(rh[i])

# print(rh)


from math import copysign


def main():
    a = [int(c) for c in input().split()]
    assert 0 not in a
    k = len(a)
    prv = []
    cur = []
    for i, e in enumerate(a):
        if i % 2:
            cur.append(a[i])
        else:
            prv.append(a[i])
    n = len(prv)
    if len(cur) < n:
        cur.append(0)
    if copysign(1, prv[0]) != copysign(1, cur[0]):
        return 0
    for r in range(k-2):
        # print(prv)
        nxt = [cur[0] * prv[i] - prv[0] * cur[i] for i in range(1, n)] + [0]
        if nxt == [0] * n:
            for i in range(n):
                nxt[i] = cur[i] * (k - r - 2*i)
        prv, cur = cur, nxt
        if copysign(1, prv[0]) != copysign(1, cur[0]) or cur[0] == 0:
            return 0
    return 1


for _ in range(int(input())):
    print(main())


from math import copysign


def main():
    a = [int(c) for c in input().split()]
    assert 0 not in a
    k = len(a)
    prv = []
    cur = []
    for i, e in enumerate(a):
        if i % 2:
            cur.append(a[i])
        else:
            prv.append(a[i])
    n = len(prv)
    if len(cur) < n:
        cur.append(0)
    if copysign(1, prv[0]) != copysign(1, cur[0]):
        return 0
    for r in range(k):
        # print(prv)
        nxt = [cur[0] * prv[i] - prv[0] * cur[i] for i in range(1, n)] + [0]
        if nxt == [0] * n:
            for i in range(n):
                nxt[i] = cur[i] * (k - r - 2*i)
        prv, cur = cur, nxt
        if copysign(1, prv[0]) != copysign(1, cur[0]) or cur[0] == 0:
            return 0
    return 1


for _ in range(int(input())):
    print(main())


# cook your dish here
t = int(input())
for _ in range(t):
    coef = list(map(int,input().split()))
    #print(coef)
    mpow = len(coef)-1
    row1 = []
    row2 = []
    mat = []
    for i in range(len(coef)):
        if i%2==0:
            row1.append(coef[i]) 
        else:
            row2.append(coef[i])
    if (len(coef))%2:
        row2.append(0)
    mat.append(row1)
    mat.append(row2)
    #print(mat)
    idle = [0]*len(row1)
    for i in range(2,len(coef)):
        rown = []
        for j in range(1,len(row1)):
            val = mat[i-1][0]*mat[i-2][j]-mat[i-2][0]*mat[i-1][j]
            rown.append(val)
        for _ in range(len(rown),len(row1)):
            rown.append(0)
        #print(rown)
        mat.append(rown)
        if rown == idle:
            for i in range(len(mat)):
                if mat[i]==idle:
                    for j in range(len(mat[i])):
                        mat[i][j] = mat[i-1][j]*(mpow+4-(i+1)-2*(j+1))
        
    #print(mat)
    #print(idle)
    s = 0
    sa = 0
    for i in mat:
        s += i[0]
        sa += abs(i[0])
    c = 0
    '''for i in range(len(mat)):
        if mat[i]==idle:
            for j in range(len(mat[i])):
                mat[i][j] = mat[i-1][j]*(mpow+4-(i+1)-2*(j+1))'''
    #print(mat)
    if(s==sa):
        c = 1
        for i in range(len(mat)):
            if mat[i][0]==0:
                c = 0
                break
    print(c)