Năm nay, kỳ thi học sinh giỏi Duyên hải và Đồng bằng Bắc Bộ được tổ chức tại tỉnh Thái Nguyên. Thầy Hiếu muốn tạo một sân chơi bổ ích cho các học sinh tham dự nên đã đưa ra một trò chơi.

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

Bạn cần xem lại thống kê của ~q~ màn chơi ~a_1,a_2,\dots,a_q~.

Yêu cầu: Hãy cho biết sức mạnh của Boss trong mỗi màn chơi cần xem.

Input

• Dòng thứ nhất chứa số nguyên ~q~;

• Dòng thứ hai chứa ~q~ số nguyên ~a_1,a_2,\dots,a_q~.

Output

In ra ~q~ số nguyên trên cùng một dòng. Số thứ ~i~ là sức mạnh của Boss thứ ~a_i~ ~(1 \le i \le q)~. Các số được phân tách bởi một dấu cách.

Scoring

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

Notes

Gọi ~G(x)~ là tổng các ước nguyên dương của ~x~.

Trong ví dụ thứ nhất:

~G(2)=1+2=3~;

~G(4)=1+2+4=7~;

~G(10)=1+2+5+10=18~;

~G(9)=1+3+9=13~.

Ví dụ thứ hai là một ví dụ cho subtask ~4~:

~G(10)=18~;

~G(11)=1+11=12~;

~G(12)=1+2+3+4+6+12=28~;

~G(13)=1+13=14~.