Sau khi bán bánh mì nhưng vẫn không có lời DeMen100ms chuyển sang công việc trồng cây. Khu vườn của DeMen100ms có khoảng \(10^{18}\) cây và mỗi cây được đánh mỗi số, cây đầu tiên đánh số \(1\), hai cây tiếp theo đánh số \(2\), ba cây tiếp theo đánh số \(3\), ... \(k\) cây tiếp theo đánh số \(k\). DeMen100ms muốn chọn ra T cây để xây tổ ấm để tránh cơn bão sắp vào miền trung.

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(T \leq 10^5\)).
• \(T\) dòng tiếp theo chứa số nguyên \(c_i\) (\(c_i \leq 10^{18}\)).

Output

• In ra \(T\) dòng mỗi dòng in ra số được đánh của cây thứ \(c_i\).

Example

2
5
1

3
1