Informath là một sản phẩm robot của câu lạc bộ LQĐ 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\) byte dữ liệu (với \(a\) là một số nguyên dương) trong thời gian \(b\) giây \((b \ge 2)\).

Cụ thể, với tập tin kích thước \(n\), robot có thể đọc dữ liệu theo cách:

• Lần đầu đọc \(a_1^{b_1}\) byte trong \(b_1\) giây,
• Nếu còn dữ liệu, tiếp tục đọc \(a_2^{b_2}\) byte trong \(b_2\) giây, Quá trình lặp lại đến khi đọc hết tập tin. Mục tiêu là tìm cách đọc nhanh nhất sao cho tổng thời gian đọc dữ liệu là ít nhất.

Như vậy ta có \(n = a_1^{b_1} + a_2^{b_2} .. a_k^{b_k}\) và thời gian đọc là \(b_1 + b_2 .. + 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, 4 = 2^2, 2024 = 42^2 + 16^2 + 2^2\)
• \(60 = 4^2 * (8 \times 1 + 7)\) có dạng \(4^k \times (8 \times 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 có kích thước \(n\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên \(T\) \((1 \le T \le 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 \le n \le 10^9)\) – kích thước tập tin.

Dữ liệu ra:

• 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 file dữ liệu.

Ràng buộc:

• 20% số test có \(T\) tập tin với kích thước không vượt quá \(2^8\).
• 40% số test có tổng kích thước tập tin thỏa mãn \(2^8 < N \le 2^{16}\).
• 40% số test có tổng kích thước tập tin thỏa mãn \(2^{16} < N \le 10^9\).

Input 1

1
100000000

Output 1

2

Giải thích

• \(100000000 = 10000^2\) (𝑎 = 10000, 𝑏 = 2)

Input 2

3
27
128
33

Output 2

3
4
5

Giải thích

• \(27 = 3^3 (a=3, b=3)\)
• \(128 = 8^2 + 8^3 (a_1=8, b_1=2; a_2=8, b_2=2)\)
• \(33 = 5^2 + 2^3 (a_1=5, b_1=2; a_2=2, b_2=3)\)