Description

Help! Help! We're all gonna be flunked by these devil-like TAs!

── Students

It's said that there's a course that every student who take that course will be flunked...

The course might be Advanced Calculus, Complex Analysis ... it could be Introduction to Programming! Who knows?

The only thing you know is that the professor of this course is Professor Chen-Tzong Hwann(煥陳宗), a.k.a. CTH. His TAs keep producing extremely hard problems, leads that every student are going to be flunked.

However, flunking every student means that CTH needs to submit a report to the administration of the university, and CTH is too lazy to write that report, so he decide to let exactly one student pass.

---

The class have $n$ students, CTH will organize a tournament. The tournament is going to be held with the following format:

1. If there's only one student remaining, then the student is the winner, the tournament ends.

2. If the number of remaining students is even, they split in pairs and compete for each pair. The loser of each pair will be eliminated(no draws for this competition).

3. Otherwise, if the number of remaining students is odd, they'll compete each other once in round robin tournament and decide the final winner, then the tournament ends.

   • For the round robin tournament part, if there are $x$ students remaining, there will be $\frac{x(x-1)}2$ competitions since they compete with everyone once.

For example, if there are 20 students initially, they would have 10 competitions, then 10 students are eliminated. The remaining 10 students would have 5 competitions and remain 5 students, then have 10 competitions for round robin tournament. Totally there are 10+5+10=25 competitions.

CTH's TA want to see exactly $n$ competitions in order to see them suffer. He asks you to calculate the minimum number of students that the course need to have.

---

Hint:

This problem involves brute force(暴力搜尋) and binary search(二分搜尋). One of the solutions is to combine the two techniques. You may try to think what we can enumerate, and what we can do a binary search.

Brute Force: usually applied when the number is small.

Binary Search: If the sequence is in increasing / decreasing order, the binary search technique can be applied.

Input

The first line contains an integer $T$. There are $T$ testcases below. $1\le T\le 64$.

There are $T$ lines below. Each line contains exactly one integer $n$, the number of competitions.

$1\le n\le 10^{18}$.

Output

For each testcase, output its minimum number of students that the course need to have with newline.

If there's no such answer, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss