Cho một dãy số nguyên dương ~a~ độ dài ~n~. Với một loại thao tác duy nhất là tăng giá trị của một phần tử bất kì trong dãy lên 1 đơn vị.

Yêu cầu: Với mỗi mỗi ~k~ thuộc đoạn ~[2, n]~, bạn hãy tính xem tổng số thao tác ít nhất cần dùng để cả mảng là bội của ~k~.

Input

Dòng đầu gồm một số nguyên duy nhất là ~n~ (~n\le 5\times 10^5~) độ dài mảng

Dòng thứ hai gồm ~n~ giá trị nguyên dương ~a_i~ (~a_i\le 5\times 10^5~)

Output

Gồm ~n-1~ dòng mỗi dòng là số thao tác cần để cả dãy là bội của ~k~ với mọi ~k~ thuộc khoảng ~[2, n]~

Sample Input 1

4
1 4 2 2

Sample Output 1

1
6
7

Sample Input 2

8
6 3 5 9 1 4 7 1

Sample Output 2

6
9
16
19
24
27
36

Scoring

• Có ~40\%~ số điểm thỏa mãn ~n \le 5000~