Nhận thấy các con của mình rất chăm học thuật toán nên bố Tài SC (super cute) đã ra cho chúng một bài toán ngây thơ như sau: cho ~q~ số nguyên dương (không nhất thiết phân biệt), hãy tính tổng ước của từng số. Các con cảm thấy rất giận dỗi vì lại ra một bài căn bản như thế, cho đến khi chúng đọc được kỹ các subtask, hãy làm thử bài toán này của bố Tài nhé.

Input

Dòng đầu tiên là số nguyên dương ~q~.

Dòng tiếp theo là ~q~ số nguyên dương ~a_1, a_2, ..., a_q.~

Output

In ra ~q~ số là đáp số của bài toán.

Sample input

4
2 4 10 9

Sample output

3 7 18 13

Subtasks

• Subtask 1 (15% số điểm): ~q ≤ 10^4; a_i ≤ 10^3~ với ~(1 ≤ i ≤ q)~
• Subtask 2 (25% số điểm): ~q ≤ 10^5; a_i ≤ 10^5~ với ~(1 ≤ i ≤ q)~
• Subtask 3 (35% số điểm): ~q ≤ 10^5; a_i ≤ 10^6~ với ~(1 ≤ i ≤ q)~
• Subtask 4 (25% số điểm): ~q ≤ 10^6; a_i ≤ 10^{12}~ và ~a_{i+1} = a_i + 1~ với ~1 ≤ i <q.~</li>