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 các màn chơi ~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~.
• Dòng thứ hai gồm ~q~ số: ~a_{1}, a_{2}, \ldots, a_{q}~ , được ghi cách nhau bởi dấu cách.

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 \leq i \leq n)~. 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~.

Chấm điểm

• Subtask 1(15%): ~q \leq 10^{4}, a_{i} \leq 10^{3} (1 \leq i \leq q~;
• Subtask 2(25%): ~q \leq 10^{5}, a_{i} \leq 10^{5} (1 \leq i \leq q)~.
• Subtask 3(35%): ~q \leq 10^{5}, a_{i} \leq 10^{6} (1 \leq i \leq q)~.
• Subtask 4(25%): ~q \leq 10^{6}, a_{i} \leq 10^{12} (1 \leq {i} \leq q)~, ~a_{i+1}=a_i+1 (1 \leq i < q)~.