Рабочее место участника

Однажды конструктор Трурль решил создать Вечный Двигатель.

- Работа этой машины описывается функцией вида `f(x)\ =\ A*x^2\ +\ B*x\ +\ C`, – сказал Трурль Клапауцию. – Если уравнение `f(x)\ =\ 0` имеет действительные решения, то Двигатель будет работать вечно. Сейчас я решу это простое квадратное уравнение и …

- Вздор! Твоя машина не будет работать вечно, так как `x` каждую секунду изменяется на 1, а результат накапливается, – возразил Клапауций. – Таким образом, нужно рассматривать функцию `g(x,\ k)\ =\ f(x)\ +\ f(x+1)\ +\ f(x+2)\ +\ …\ +\ f(x+k)`, не `f(x)`. Как только у уравнения `g(x,\ k)\ =\ 0` не будет действительных решений, твой Вечный Двигатель остановится!

- Ничего страшного, – ответил Трурль. – Думаю, я смогу подобрать параметры `A`, `B` и `C` таким образом, чтобы машина никогда не останавливалась.

- Ничего у тебя не получится! – саркастически воскликнул Клапауций и отправился домой.

"Ну, если не вечность, то хотя бы миллиард секунд, а там, глядишь, Клапауций и забудет о машине", – подумал Трурль, принимаясь за расчеты. – "Так, сумма первых `k` квадратов равна `k*(k+1)(2*k+1)/6`"…

Напишите программу для Трурля, которая по введенным коэффициентам `A`, `B` и `C` определяет время работы машины, то есть находит такое минимальное целое `k\ ≥\ 0`, при котором уравнение `g(x,\ k)\ =\ 0` не имеет действительных решений.

Во входном файле в первой строке содержится целое число `N` (`1\ ≤\ N\ ≤\ 1000`) – количество вариантов, которые Трурль хочет рассчитать. Далее следует `N` строк, в каждой строке содержится три целых числа `A`, `B` и `C`, разделенные одним пробелом (`0\ <\ A\ ≤\ 10^6`, `|B|\ ≤\ 10^6`, `|C|\ ≤\ 10^6`).

В выходной файл для каждого варианта вывести на отдельной строке ожидаемое время работы машины `k`. Если `k\ >\ 10^9`, то вывести число 1000000000.

2
1 -2 1
1 1 -6

1
8