To read the problem statement in English, choose the language using the flag on the navigation bar.

Trong giờ ra chơi, nhóm gồm ~n~ bạn học sinh rủ nhau chơi nhảy dây. Trong mỗi lượt chơi sẽ có hai bạn được chọn để quăng dây, và một bạn được chọn để nhảy dây. Hai bạn quăng dây sẽ cầm hai đầu sợi dây, một bạn quăng dây theo chiều kim đồng hồ, và bạn còn lại quăng ngược chiều kim đồng hồ, để dây liên tục chạm đất và quăng qua đầu người nhảy. Người nhảy phải đứng giữa hai người quăng và phải nhảy khi dây chạm đất. Nếu như dây chạm vào chân bạn nhảy, bạn nhảy sẽ thua cuộc.

Tất cả ~n~ bạn đều rất khỏe mạnh và năng động, nên các bạn có độ dẻo dai lần lượt là ~c_1, c_2, \ldots, c_n~.

Nếu như bạn thứ ~i~ được chọn làm bạn nhảy dây, trong ~c_i~ giây bạn ấy sẽ đứng ở trên mặt đất, sau đó bạn ấy nhảy và trong ~c_i~ giây tiếp theo chân bạn ấy không chạm đất, và quá trình này sẽ lặp lại. Ví dụ, nếu ~c_i = 3~:

• Tại giây ~1, 2, 3~ chân bạn ấy chạm đất.

• Tại giây ~4, 5, 6~ chân bạn ấy không chạm đất.

• Tại giây ~7, 8, 9~ chân bạn ấy chạm đất.

• Tại giây ~10, 11, 12~ chân bạn ấy không chạm đất.

• ~\ldots~

Nếu như bạn thứ ~u~ và ~v~ được chọn làm hai bạn cầm dây, dây mà hai bạn quăng sẽ chạm đất vào các thời điểm là bội của ~gcd(c_u, c_v)~, trong đó ~gcd(x, y)~ được định nghĩa là ước chung lớn nhất của hai số nguyên ~x~ và ~y~. Ví dụ, với ~c_u = 6~ và ~c_v = 8~, ~gcd(6, 8) = 2~, nên dây mà hai bạn này quăng sẽ chạm đất tại các giây ~2, 4, 6, 8, 10, \ldots~

Cho danh sách độ dẻo dai của ~n~ bạn. Với bạn thứ ~i~, hãy đếm xem có bao nhiêu cặp bạn quăng dây ~u~ và ~v~ (~u < v~), sao cho nếu như bạn thứ ~i~ là người nhảy dây, thì bạn này sẽ không bao giờ thua.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~3 \le n \le 10^6~) là số lượng bạn học sinh rủ nhau chơi nhảy dây.

Dòng tiếp theo chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le 10^6~) lần lượt là độ dẻo dai của ~n~ bạn học sinh.

Output

In ra ~n~ số nguyên. Số thứ ~i~ cần in ra là là số lượng cặp bạn học sinh có thể chọn làm bạn quăng dây sao cho nếu ~i~ được chọn làm bạn nhảy dây thì bạn này sẽ không bao giờ thua.

Scoring

• Subtask 1, ứng với ~65~ điểm, có ~n \le 100~.

• Subtask 2, ứng với ~65~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~130~ điểm.

Sample Input 1

3
1 6 8

Sample Output 1

1 0 0

Sample Input 2

12
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 2

15 3 1 0 0 0 0 0 0 0 0 0

Notes

Trong ví dụ đầu tiên:

• Nếu bạn đầu tiên được chọn làm bạn nhảy, các thời điẻm chân của bạn ấy không chạm đất là các giây ~2, 4, 6, 8, \ldots~ do ~c_1 = 1~. Bạn thứ hai và ba có thể chọn làm cặp bạn quăng dây, do ~c_2 = 6, c_3 = 8~, ~gcd(6, 8) = 2~, và thời điểm dây mà hai bạn quăng chạm đất cũng sẽ là các giây ~2, 4, 6, 8, \ldots~.

• Nếu bạn thứ hai được chọn làm bạn nhảy, bạn ấy sẽ thua nếu bạn thứ nhất và thứ ba quăng dây, bởi vì ~gcd(1, 8) = 1~, do đó dây chạm đất tại mọi giây nguyên. Điều này cũng tương tự nếu bạn thứ ba được chọn làm bạn nhảy.

Fun fact: trong tiếng Anh, trò chơi được mô tả trong đề bài giống trò chơi Double Dutch hơn là trò chơi Skipping rope, nhưng được chơi bằng một dây thay vì hai dây.