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 \leq i \leq 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 \leq n \leq 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~x_1, x_2, ..., x_n~ (~1 \leq x_i \leq 10^{18}~, ~1 \leq i \leq 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 \leq 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 \leq 10~ hoặc ~1 + 9 \leq 10~.

SUBTASKS

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