Số chính phương là số mà nếu lấy căn bậc hai của nó thì được một số nguyên dương. Hay nói cách khác, bình phương của một số nguyên dương là một số chính phương. Ví dụ: 9 là số chính phương vì $\sqrt{9}=3$ (hay $3^2=9$), nên 9 là số chính phương. Nhưng 10 thì không phải số chính phương vì $\sqrt{10}\approx 3,16228$.

Yêu cầu: Cho $n$ số nguyên dương $x_1,x_2,...,x_n$. Tương ứng với mỗi $x_i$ ($1\le i\le n$), hãy cho biết có nhiều nhất bao nhiêu số chính phương khác nhau mà tổng của chúng không vượt quá $x_i$.

INPUT

• Dòng đầu chứa số nguyên dương $n$ ($1\le n\le {10}^5$).
• Dòng thứ hai chứa $n$ số nguyên dương $x_1,x_2,...,x_n$ ($1\le x_i\le {10}^{18}$, $1\le i\le n$).

OUTPUT

$n$ số nguyên trên cùng một dòng trong đó số thứ $i$ là đáp án cần tìm tương ứng của $x_i$.

SAMPLE INPUT

2
14 10

SAMPLE OUTPUT

3 2

Giải thích:

• Với $x_1=14$ ta chỉ có thể chọn nhiều nhất $3$ số chính phương là $1,4,9$ vì $1+4+9\le 14$.
• Với $x_2=10$ ta chỉ có thể chọn nhiều nhất $2$ số chính phương là $1$ và $4$ hoặc $1$ và $9$ vì $1+4\le 10$ hoặc $1+9\le 10$.

SUBTASKS

• $50\mathrm{\%}$ test tương ứng với $50\mathrm{\%}$ số điểm có $1\le n\le {10}^3,1\le x_i\le {10}^9$.
• $50\mathrm{\%}$ test tương ứng với $50\mathrm{\%}$ số điểm còn lại không có ràng buộc gì thêm.