(ncp.*)

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},\ldots,\ 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}\).

Dữ liệu vào:

+ 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 \(x_{1},x_{2},\ldots,x_{n}\) \(\left( 1 \leq x_{i} \leq 10^{18};\ 1 \leq i \leq n \right).\)

Kết quả: ghi \(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}\).

Ví dụ:

Giới hạn:

+ 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.