Tổng ước

Cho dãy số \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, 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ữ liệu vào có cấu trúc như sau:

• 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, \ldots, a_n\) \((a_i \le 10^6;\ 1 \le i \le n)\).

Ràng buộc:

• 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.

Output

In ra 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\).

Example

Input:

4
2 4 10 9

Output:

3 7 18 13

Note

Các ước của \(2\) là \(1, 2\) nên tổng là \(3\); các ước của \(4\) là \(1, 2, 4\) nên tổng là \(7\); các ước của \(10\) là \(1, 2, 5, 10\) nên tổng là \(18\); các ước của \(9\) là \(1, 3, 9\) nên tổng là \(13\).