题目描述

A triangle is a Heron's triangle if it satisfies that the side lengths of it are consecutive integers $t - 1$, $t$, $t + 1$ and that its area is an integer. Now, for given $n$ you need to find a Heron's triangle associated with the smallest $t$ bigger than or equal to $n$.

输入格式

The input contains multiple test cases. The first line of a multiple input is an integer $T$ ($1 \le T \le 30000$) followed by $T$ lines. Each line contains an integer $N$ ($1 \le N \le 10^{30}$).

输出格式

For each test case, output the smallest $t$ in a line. If the Heron's triangle required does not exist, output $-1$.

4
1
2
3
4

4
4
4
4