Informat là một sản phẩm robot của câu lạc bộ LQD IT.
Tập tin dữ liệu huấn luyện cho robot có kích thước không quá ~10^9~ byte. Trong quá trình huấn luyện, Robot đọc mỗi lần ~a^b~ byte dữ liệu (~a, b~ là các số nguyên dương nào đó và ~b \geq 2~) với thời gian đọc là ~b~ giây.

Cụ thể, với tập tin kích thước ~n~, robot đọc ~a_1^{b_1}~ (~a_1^{b_1} \leq n~) byte và tốn ~b_1~ giây. Nếu ~n - a_1^{b_1} > 0~, robot đọc tiếp ~a_2^{b_2}~ byte và tốn ~b_2~ giây, cứ như thế robot đọc hết tập tin sau ~k~ lần. Như vậy, ta có:
~n = a_1^{b_1} + a_2^{b_2} + \dots + a_k^{b_k}~ và thời gian đọc là ~b_1 + b_2 + \dots + b_k~.

Kiến thức bổ túc:

• "Các số tự nhiên luôn có thể biểu diễn thành tổng của không quá ~4~ số chính phương (số chính phương là bình phương của một số tự nhiên). Ngoại lệ, các số có dạng ~4^k * (8 * m + 7)~ thì không thể biểu diễn thành tổng của ít hơn ~4~ số chính phương (~k, m~ là số tự nhiên)."

Ví dụ:

• ~30 = 5^2 + 2^2 + 1^2; 42 = 2024 = 42^2 + 16^2 + 2^2~;
• ~60 = 4^1 * (8 * 1 + 7)~ có dạng ~4^k * (8 * m + 7)~ nên được biểu diễn từ 4 số chính phương trở lên: ~60 = 6^2 + 4^2 + 2^2 + 2^2.~

Yêu cầu: Cho số nguyên ~n~. Tính thời gian tối thiểu để robot đọc hết tập tin kích thước ~n~.

Dữ liệu: Vào từ file văn bản HOCMAY.INP

• Dòng đầu chứa số nguyên ~T (1 \leq T \leq 5)~ - số tập tin dữ liệu huấn luyện;
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n (1 \leq n \leq 10^9)~ - kích thước tập tin.

Kết quả: Ghi ra file văn bản HOCMAY.OUT gồm ~T~ dòng, mỗi dòng là thời gian ít nhất để đọc tập tin có kích thước tương ứng trong tệp dữ liệu.

Ví dụ:

Ràng buộc:

• Gọi ~N~ là tổng kích thước của ~T~ tập tin:
  • Có ~20\%~ số test thỏa ~T~ tập tin đều có kích thước không vượt quá ~2^{28}~;
  • Có ~40\%~ số test thỏa ~2^{28} < N \leq 2^{16}~;
  • Có ~40\%~ số test thỏa ~2^{16} < N \leq 10^9.~