Bạn đang chơi một trò chơi một người chơi, mà trong đó bạn sẽ phải chơi ~10^{12}~ màn chơi khác nhau để tiêu diệt ~10^{12}~ con Boss khác nhau. Màn chơi thứ ~i~ sẽ xuất hiện con Boss thứ ~i~ có chỉ số sức mạnh bằng tổng của các ước nguyên dương của ~i~.

Bạn đang cần xem lại thống kê của ~q~ màn chơi: ~a_1, a_2, \ldots , a_q~. Hãy cho biết sức mạnh của Boss của mỗi màn chơi đang xem nhé!

Dữ liệu

• Dòng thứ nhất chứa duy nhất số ~q~ ~(q \le 10^6)~.

• Dòng thứ hai lần lượt chứa ~q~ số: ~a_1, a_2, \ldots, a_q~ ~(1 \le a_i \le 10^{12})~.

Kết quả

• In ra một dòng gồm ~q~ số, số thứ ~i~ in ra sức mạnh của con Boss thứ ~a_i~ ~(1 \le i \le q)~. Các số được in ra cách nhau một khoảng trống.

Ví dụ

Sample Input 1

4
2 4 10 9

Sample Output 1

3 7 18 13

Sample Input 2

4
10 11 12 13

Sample Output 2

18 12 28 14

Giải thích

Gọi ~G(x)~ là tổng các ước của ~x~.

Test ví dụ 1 có: ~G(2) = 1 + 2 = 3~; ~G(4) = 1 + 2 + 4 = 7~; ~G(10) = 1 + 2 + 5 + 10 = 18~; ~G(9) = 1 + 3 + 9 = 13~.

Test ví dụ 2 là một ví dụ cho subtask 4. Ta có: ~G(10) = 18~; ~G(11) = 1 + 11 = 12~; ~G(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28~; ~G(13) = 1 + 13 = 14~.

Điểm số

• Subtask 1 (15%): ~q \le 10^4; a_i \le 10^3 (1 \le i \le q)~

• Subtask 2 (25%): ~q \le 10^5; a_i \le 10^5 (1 \le i \le q)~

• Subtask 3 (35%): ~q \le 10^5; a_i \le 10^6 (1 \le i \le q)~

• Subtask 4 (25%): ~q \le 10^6; a_i \le 10^{12} (1 \le i \le q); a_{i+1} = a_i + 1 (1 \le i < q)~