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à `c1,c2,...,cn`. Nếu như bạn thứ `i` được chọn làm bạn nhảy dây, trong 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 `.....` 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, ...` 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ẽ $\text{không bao giờ thua.}$ `INPUT` Dòng đầu tiên chứa số nguyên dương `n (3<=n<=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,...,c_n (1<=c_i<=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.