Trong không khí rộn ràng của ngày Tết, shiba ngồi bên hiên nhà, ngắm nhìn những cành mai vàng khoe sắc và những phong bao lì xì đỏ rực. Anh vừa nhận được một túi hoa mai vàng cùng \(N\) bao lì xì từ mẹ, mỗi bao lì xì đều ghi một con số may mắn.

Mỗi bao lì xì được ghi một con số may mắn \(a_i\). shiba chợt nghĩ ra một trò chơi thú vị. Cậu có thể buộc hai bao lì xì \(x\) và \(y\) với nhau, sau đó phải tặng hoa mai cho mẹ với số lượng tối thiểu là \(min(a_x \ \ mod \ \ a_y,a_y \ \ mod \ \ a_x)\).

shiba muốn buộc các bao lì xì lại sao cho khi nhấc một bao lì xì lên, toàn bộ các bao lì xì khác cũng được nhấc lên cùng. Mỗi bao lì xì có thể được kết nối với bất kỳ số lượng bao lì xì nào khác. Tuy nhiên, vì số lượng hoa mai của shiba có hạn, cậu nhờ bạn tính toán số lượng hoa mai ít nhất cần tặng để kết nối tất cả các bao lì xì.

Yêu cầu: Bạn hãy viết chương trình tính ra số lượng hoa mai ít nhất shiba cần tặng để có thể kết nối tất cả các bao lì xì.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^5)\).
• \(N\) dòng tiếp theo mỗi dòng chứa một số nguyên dương \(a_i\) \((1 \le a_i \le 10^7)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(N \le 1000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
4 
9 
15

4