p(x) = p_kx^k + ... + p₀x⁰ 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 p₀, p₁ ... appear, separated by spaces.

Output

Each line of the output is the solution for the following polynomials. It should 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