Sau một thời gian nghiên cứu, Nam đã đưa ra một phương pháp mã hoá các số nguyên thông qua dãy các phân số. Với số nguyên dương ~k~, một dãy hữu hạn các phân số ~a_i~ được định nghĩa như sau:

• ~a_1~ = ~\frac{1}{k}~

• ~a_i~ = ~\frac{x_i}{y_i}~ = ~\frac{x_{i-1}+1}{y_{i-1}-1}~ khi ~i>1~ với ~\frac{x_i}{y_i}~ là một phân số tối giản;

• Khi ~a_i~ đạt đến một giá trị nguyên ~n~, dãy phân số kết thúc (~y_i~ = ~1~).

Nam mã hoá hàm số ~f(k)=n~.

Ví dụ: với ~k=20~ có dãy biến như đổi sau:

~\frac{1}{20}~ -> ~\frac{2}{19}~ -> ~\frac{3}{18}~ = ~\frac{1}{6}~ -> ~\frac{2}{5}~ -> ~\frac{3}{4}~ -> ~\frac{4}{3}~ -> ~\frac{5}{2}~ -> ~\frac{6}{1}~ = ~6~

Kết quả ~f(20)=6~.

Yêu cầu: Cho số nguyên dương ~x~, bạn hãy giúp Nam tính ~f~(~x^3~ ).

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(T≤100)~ là số lượng giá trị ~x~ cần tính ~f~(~x^3~ );
• Mỗi dòng trong số ~T~ dòng tiếp theo chứa một số nguyên dương ~x~.

Kết quả: Ghi ra ~T~ dòng, mỗi dòng là giá trị ~f~(~x^3~) tương ứng với số nguyên dương ~x~ trong dữ liệu vào.

Ràng buộc:

• Số test ứng với 50% số điểm của bài có: ~x ≤ 100~;
• Số test khác ứng với 30% số điểm của bài có: ~x ≤~ ~10^4~;
• Số test còn lại ứng với 20% số điểm của bài có: ~x~ ≤ ~10^6~.

Ví dụ:

INPUT

2
3
4

OUTPUT

6
12