Cho dãy số ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Viết chương trình tính tổng các ước dương của mỗi phần tử trong dãy ~a~.

Input

• Dòng 1: Chứa số nguyên dương ~n~ (~n \le 10^6~);
• Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^6~; ~1 \le i \le n~).

Output

Ghi ra gồm một dòng chứa ~n~ số nguyên, số thứ ~i~ là tổng các ước dương của phần tử ~a_i~.

Sample Input 1

4
2 4 10 9

Sample Output 1

3 7 18 13

Subtasks

• Có 40% số test ứng với 40% số điểm của bài có ~n = 1~;
• Có 30% số test ứng với 30% số điểm của bài có ~1 < n \le 10^3~;
• 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc.