Trong một lần đi dạo chơi quanh trường THPT chuyên Lê Hồng Phong rộng lớn thì Informath, con robot thích Toán nhưng yêu lập trình, đã vô tình lạc vào tòa nhà thư viện. Quá choáng ngợp với sự đồ sộ của nơi này, robot đã muốn tìm học hết các sách vở ở trong đó. Kho tàng tri thức trong thư viện không chỉ có sách in mà còn có một số tài liệu quý được số hóa thành ~T~ tập tin. Mỗi tập tin có kích thước không quá ~{{10}^{9}}~ kilobyte và robot sẽ lần lượt đọc chúng. Bộ xử lý của robot được thiết kế rất đặc biệt. Với mỗi tập tin, nó không đọc dữ liệu theo từng kilobyte mà mỗi lần sẽ đọc hết một lượng có kích thước ~{{a}^{b}}~ kilobyte, ở đây ~(a,b)~ là các số nguyên dương nào đó và ~b\ge 2;~ lúc này, nó sẽ tốn thời gian ~b~ giây cho dù giá trị của ~a~ là mấy.

Cụ thể hơn, với một tập tin kích thước ~n,~ đầu tiên, robot chọn một cặp ~({{a}_{1}},{{b}_{1}})~ như mô tả trên mà ~a_{1}^{{{b}_{1}}}\le n~ và tốn ~{{b}_{1}}~ giây để đọc; nếu như ~n-a_{1}^{{{b}_{1}}}>0~ thì vẫn còn thông tin chưa đọc xong, nó sẽ chọn tiếp một cặp ~({{a}_{2}},{{b}_{2}})~ nữa rồi tốn ~{{b}_{2}}~ giây để đọc phần tri thức còn lại và cứ thế, giả sử tổng cộng cần ~k~ lần. Như vậy, có ~k~ cặp số nguyên dương ~({{a}_{i}},{{b}_{i}}),\text{ }1\le i\le k~ và các số ~{{b}_{i}}\ge 2~ sao cho

~n=a_{1}^{{{b}_{1}}}+a_{2}^{{{b}_{2}}}+\cdots +a_{k}^{{{b}_{k}}}.~

Tổng thời gian robot cần sử dụng cho tập tin kích thước ~n~ này sẽ là ~{{b}_{1}}+{{b}_{2}}+\cdots +{{b}_{k}}.~
Anh quản lý thư viện, cũng là người yêu Toán và thích lập trình, đã tạo điều kiện thuận lợi cho Informath có thể kết nối đến máy chủ để đọc được các dữ liệu. Tuy vậy, cách đọc của robot làm anh liên tưởng đến một tính chất về biểu diễn số học khá thú vị như sau: "mỗi số tự nhiên luôn có thể viết thành tổng của không quá ~4~ số chính phương (chú ý, số chính phương là bình phương của một số tự nhiên); ngoài ra, các số có dạng đặc biệt là ~{{4}^{k}}(8m+7)~ với ~k,m~ là các số tự nhiên, thì không thể viết thành tổng của ít hơn ~4~ số chính phương được".

Ví dụ ~30={{5}^{2}}+{{2}^{2}}+{{1}^{2}},\text{ 4}={{2}^{2}},\text{ }2024={{42}^{2}}+{{16}^{2}}+{{2}^{2}}~ (nói thêm là các số này vẫn có thể biểu diễn được bởi tổng của nhiều số chính phương hơn, nhưng theo tính chất trên, luôn có cách biểu diễn chúng bởi tổng của không quá ~4~ số chính phương); còn số ~60=4\cdot (8\cdot 1+7)~ có dạng ~{{4}^{k}}(8m+7)~ nên cần dùng đến ~4~ số chính phương trở lên mới biểu diễn được nó, chẳng hạn ~{{6}^{2}}+{{4}^{2}}+{{2}^{2}}+{{2}^{2}}~ (không có cách nào dùng ít hơn ~4~ số chính phương). Anh quản lý thư viện đã chia sẻ tính chất trên cho Informath biết và robot thấy rằng sự thật thú vị này đúng là có liên quan ít nhiều đến cách đọc dữ liệu của nó, dù robot có thể xử lý được cả các số mũ lớn hơn ~2~ chứ không nhất thiết chỉ là các số chính phương. Từ sự gợi ý tình cờ đó, robot đã suy luận thêm và tính toán ra được phương án đọc dữ liệu nhanh nhất có thể, hãy cùng robot giải quyết vấn đề này nhé.

Yêu cầu: Để đọc hết lượng tri thức trong từng tập tin, hỏi Informath cần tốn ít nhất mấy giây (coi như thời gian nghỉ giữa hai lần liên tiếp để chọn các cặp số là không đáng kể)?

Input dòng đầu chứa ~T~ là số tập tin với ~1\le T\le 5.~ Trên ~T~ dòng tiếp theo, mỗi dòng sẽ có một số nguyên dương duy nhất không vượt quá ~{{10}^{9}}.~

Output In ra ~T~ số nguyên trên các dòng khác nhau theo thứ tự cho biết thời gian ít nhất mà robot Informath cần sử dụng để đọc từng tập tin trong thư viện.

Sample input 1

1
100000000

Sample output 1

2

Sample input 2

3
27
128
33

Sample output 2

3
4
5

Giải thích

Ở test 1, ta thấy ~{{10}^{8}}={{({{10}^{4}})}^{2}}~ nên theo cách học đặc biệt của Informath, nó chỉ tốn 2 giây. Đây là thời gian ít nhất cần sử dụng.

Ở test 2:

• Có ~27={{3}^{3}}~ nên robot chỉ cần đọc 1 lần với thời gian là 3 giây, đây cũng là số nhỏ nhất.
• Có ~128={{8}^{2}}+{{8}^{2}}~ nên cần đọc 2 lần, mỗi lần 2 giây nên tổng thời gian là 4 giây. Chú ý là nếu như xét ~128={{2}^{7}}~ thì nó cần thời gian đọc đến 7 giây, là nhiều hơn. Ngoài ra, ta cũng có thể kiểm tra được rằng không thể đọc trong ít hơn 4 giây nên thời gian ít nhất cần tìm là 4.
• Có ~33={{5}^{2}}+{{2}^{3}}~ nên nó cần đọc 2 lần với tổng thời gian là ~2+3=5~, đây là số nhỏ nhất.

gọi ~N~ là tổng kích thước của ~T~ tập tin:

• Có 20% số test ứng với 20% số điểm của bài thỏa mãn ~T~ tập tin đều có kích thước không vượt quá ~{{2}^{8}}.~
• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: ~{{2}^{8}}<N\le {{2}^{16}}.~</li>
• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: ~{{2}^{16}}<N\le {{10}^{9}}.~</li>