Loli được công ty Lmao giao việc xử lý một thùng hàng có tổng khối lượng là một số nguyên dương ~n~. Loli cần phải xử lý thùng hàng đó, làm sao để chúng có được mức giá cao nhất có thể. Cách thức xử lý thùng hàng của công ty như sau:

Mỗi thùng hàng có khối lượng ~n~, và mọi số nguyên dương ~n~ đều có thể phân tích thành tích của các thừa số nguyên tố. Gọi một cách xử lý thùng hàng là một cách phân tích số ~n~ thành tích của các thừa số nguyên tố; và biểu diễn dưới dạng một chuỗi ~p~ gồm các cặp ~p_i~ có dạng ~(a, x)~.

Ví dụ: số ~100~ có thể được phân tích thành ~2^2\times 5^2~, vì vậy chuỗi ~p~ sẽ là ~[(2,2),\ (5,2)]~. Một cách xử lý khác có thể là ~10^2~, tạo ra chuỗi ~p~ là ~[(10,2)]~.

Tuy nhiên cũng có cách xử lý mà công ty không chấp nhận. Đó là những cách mà có ~a~ không phải là tích của các số nguyên tố khác nhau.

Ví dụ: số ~28~ có thể phân tích thành ~2^2\times 7^1~, vì vậy chuỗi ~p~ là ~[(2,2),\ (7,1)]~, cách xử lý này hợp lệ. Tuy nhiên một cách xử lý khác là ~4^1\times 7^1~ có chuỗi ~p~ là ~[(4,1),\ (7,1)]~ là không hợp lệ, vì có ~a=4=2\times 2~, không phải tích của các số nguyên tố khác nhau.

Một số trường hợp ~a~ không hợp lệ khác: ~12 = 2\times 2 \times 3~; ~200 = 2^3 \times 5^2~; ...

Mức giá của một cách xử lý thùng hàng chính là tổng của ~a\times x~ trong các phần tử trong chuỗi ~p~, nói cách khác, mức giá đó là ~a_1\times x_1+a_2\times x_2+\dots+a_n\times x_n~, với chuỗi ~p = [(a_1, x_1), (a_2, x_2), \dots, (a_n, x_n)]~.

Hãy tìm cách xử lý sao cho mức giá là cao nhất có thể. Chuỗi ~p~ có thể có độ dài tùy ý, miễn là cách xử lý đó hợp lệ.

Input

• Dòng đầu tiên chứa một số nguyên dương ~t\ (1\le t\le 100)~ là số test con.
• ~t~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n\ (2\le n \le 2\times 10^9)~.

Output

• ~t~ dòng, mỗi dòng chứa một số nguyên là kết quả của bài toán tương ứng.

Subtasks

• Subtask 1: ~20\%~ test có ~n \le 15~;
• Subtask 2: ~20\%~ test có ~n \le 1000~;
• Subtask 3: ~30\%~ test có ~n \le 10^5~;
• Subtask 4: ~30\%~ test không có ràng buộc gì thêm.

Sample Input 1

3
100
10
864

Sample Output 1

20
10
22

Giải thích:

Ở test đầu, ~100 = 10^2~ nên có cách xử lý là ~p = [(10,2)]~ tạo mức giá ~10\times 2 = 20~. Cách xử lý này hợp lệ vì ~10 = 2\times 5~, là tích các số chính phương riêng lẻ. Cách xử lý ~p = [(100,1)]~ không hợp lệ vì có ~100 = 2^2 \times 5^2~, không phải tích các số chính phương khác nhau.

Ở test 2, ~10 = 10^1~ nên có cách xử lý là ~p = [(10,1)]~ tạo mức giá ~10\times 1 = 10~, hợp lệ. Cách xử lý khác là ~p = [(2,1), (5,1)]~ chỉ tạo mức giá ~2\times 1 + 5\times 1 = 7~, không phải mức giá cao nhất có thể.