human
Description

Since the cubic equation: ax ^ 3 + bx ^ 2 + cx + d = 0 is given, please check the number of positive real roots and the number of negative real roots, respectively.

The number of roots shall be counted including the multiple roots.


Input

The input consists of multiple test cases, and the number is recorded on the first line.

From the second line onward, the coefficients of the cubic equation are written in the form of a b c d. a is not 0, and each number is an integer value from -100 to 100.

Output

For a given cubic equation, output the number of positive real roots and the number of negative real roots separated by a space.

Example

Input

2
1 3 3 1
-10 0 0 0

Output

0 3
0 0
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is the Python program you requested.

import sys,queue,math,copy
from fractions import gcd
input = sys.stdin.readline
INF = 10**4
EPS = 10 ** (-8)
LI = lambda : [int(x) for x in input().split()]
_LI = lambda : [int(x)-1 for x in input().split()]

N = int(input())
for _ in range(N):

    a,b,c,d = LI()
    if a < 0:
        a = -a
        b = -b
        c = -c
        d = -d
    f = lambda x: a*x*x*x + b*x*x + c*x + d

    a_plus = 0
    a_minus = 0
    D = b * b - 3 * a * c

    def count(x, y):
        global a_plus,a_minus
        if x > 0:
            a_plus += y
        elif x < 0:
            a_minus += y

    if D < 0:
        # 単調増加/減少
        count(-d,1)
    elif D == 0:
        if f(-b/(3*a)) == 0: #３重解
            count(-b,3)
        else: # 単調増加
            count(-d,1)
    else:
        x1 = (- b - math.sqrt(D)) / (3*a)
        x2 = (- b + math.sqrt(D)) / (3*a)

        def bs(h,l):
            if min(h,l) <= 0 <= max(h,l)  and f(0) == 0:
                return 0
            while f(h) > f(l) + EPS:
                m = (h + l)/2
                if f(m) > 0:
                    h = m
                else:
                    l = m
            return l

        if f(x1) > 0:
            a1 = bs(x1,-INF)
            count(a1,1)
            if f(x2) < 0:
                a1 = bs(x1,x2)
                count(a1,1)
                a1 = bs(INF,x2)
                count(a1,1)

            elif f(x2) == 0:
                count(x2,2)
        elif f(x1) == 0:
            count(x1,2)
            a1 = bs(INF,x2)
            count(a1,1)
        else: #f(x1) < 0
            a1 = bs(INF,x2)
            count(a1,1)

    print (a_plus, a_minus)