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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def solve():\r\n    c = list(map(int, input().strip().split()))\r\n    n = len(c)\r\n    if n <= 2:\r\n        print(1)\r\n        return\r\n    k = (n + 1) // 2\r\n    r = [[], []]\r\n    for i in range(n):\r\n        if i % 2 == 0:\r\n            r[0].append(c[i])\r\n        else:\r\n            r[1].append(c[i])\r\n    if len(r[1]) < k:\r\n        r[1].append(0)\r\n    r[0].append(0)\r\n    r[1].append(0)\r\n    while k > 0:\r\n        p = []\r\n        for i in range(1, k + 1):\r\n            p.append(r[-1][0] * r[-2][i] - r[-1][i] * r[-2][0])\r\n        r.append(p + [0])\r\n        k -= 1\r\n    r = [x[0] for x in r]\r\n    atleastz, allz = 0, 1\r\n    for x in r:\r\n        if x == 0:\r\n            atleastz = 1\r\n        else:\r\n            allz = 0\r\n    if atleastz:\r\n        if allz:\r\n            print(1)\r\n        else:\r\n            print(0)\r\n        return\r\n    for i in range(1, len(r)):\r\n        if r[i] * r[i - 1] < 0:\r\n            print(0)\r\n            return\r\n    print(1)\r\n\r\ndef main():\r\n    t = int(input().strip())\r\n    for _ in range(t):\r\n        solve()\r\n\r\ndef __starting_point():\r\n    main()\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13715