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^{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 \(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}} + \ldots + a_{k}^{b_{k}}\) và thời gian đọc là \(b_{1} + b_{2} + \ldots + 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} \times (8 \times 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^{1} \times (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 kích thước \(n\).

Input

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

Output

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

Scoring

Gọi \(N\) là tổng kích thước của \(T\) tập tin

• Subtask \(1\) (\(20\%\) điểm): \(T\) tập tin đều có kích thước không vượt quá \(2^{8}\).
• Subtask \(2\) (\(40\%\) điểm): \(2^{8} < N \leq 2^{16}\).
• Subtask \(3\) (\(50\%\) điểm): \(2^{16} < N \leq 10^{9}\).

Example

1
100000000

2

3
27
128
33

3
4
5