Một số tam giác là một số nguyên dương có dạng \(1+2+\dots+k\). Các số tam giác đầu tiên là \(1\), \(3\), \(6\), \(10\) và \(15\).

Mọi số nguyên dương đều có thể biểu diễn thành tổng của các số tam giác. Ví dụ, \(42=21+21\) và \(1337=1326+10+1\).

Cho một số nguyên dương \(n\), hãy xác định số lượng số tam giác ít nhất có tổng bằng \(n\).

Input

Dòng đầu tiên chứa một số nguyên \(t\): số lượng truy vấn.

Sau đó, mỗi dòng chứa một số nguyên dương \(n\).

Output

Với mỗi truy vấn, in ra số lượng số tam giác ít nhất.

Constraints

• \(1 \le t \le 100\)

• \(1 \le n \le 10^{12}\)

Example

5
1
2
3
42
1337

1
2
1
2
3