KMSL4B - Roots of polynomial

p(x)=pk x^k + ... + p0x^0 is a given polynomial of degree at most 20. Check whether all roots of p() belong to the open unit disc |z|< 1 on the complex plain.

Input

First the number of polynomials appears. Then the data for the following polynomials follows in the consecutive lines. For each of them first the degree is given, then in the following line the coefficients p0, p1, ... appear, separated by spaces.

Output

Each line of the output is the solution for the following polynomials. It shoud be '1' if the roots of p() belong to the open unit disc, or '0' otherwise.

Example

Input:
2
2
1 2 1
2
0.5 1 1

Output:
0
1

Added by:Adam Nadolski
Date:2004-12-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2010-05-04 09:41:06 :D
This is a rather hard mathematical problem. You can look for Schur-Cohn algorithm if you need help on this one.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.