Mọi kí niệm của tụi mình, anh đều giữ nguyên vẹn, chỉ tiếc là nó được đặt trong một trái tim tan vỡ...

Mở mắt ra, Koruto bất giác nhận ra anh đang ở ngôi trường cấp 2 vừa mới tốt nghiệp vài tháng trước. Trước mắt anh là những người học sinh nô đùa, những nhóm túm tụm lại với nhau, bầu không khí này gợi nhắc anh nhớ về thời cấp 2 nông nổi của mình.

Ủa.. Nhưng mà, sao mình lại ở đây ? Mình chẳng thể nhớ được gì cả...

Từ bên trong một lớp học gần đó, một hình ảnh bất chợt thu hút Koruto. Một cậu nhóc ngồi đó, thi thoảng lại quay xuống bàn sau khi cô bạn ngồi sau cậu bé không để ý. Cảm thấy tò mò, Koruto tới gần hơn. Hoá ra, cậu bé ấy tranh thủ lúc cô bạn không để ý, vẽ cô bạn vào quyển sổ cầm tay của mình.

Đây... Chẳng phải là...

Koruto nhìn kĩ hai đứa học sinh, bất chợt nhận ra những gương mặt quen thuộc...

• Này, cậu giữ giùm tớ quyển sổ này nhé !
• Hả, sao lại...
• Giữ giùm tớ đến ngày mai nhé.
• ... Được thôi.

Nói rồi cậu học sinh lấy cặp ra về, lướt ngang qua Koruto, mặt đỏ lựng...

Đúng rồi, từ trước đã có chuyện như vậy rồi nhỉ...

Quay lại nhìn cô học sinh đứng đó, lòng cậu cảm thấy có gì đó khó tả. Cô bé giở quyển sổ, lật từng trang và dừng lại rất lâu ở một trang mà nhìn không chớp mắt.

Đó là hình vẽ cô bé.

Đột nhiên, mọi thứ xung quanh nhoè dần đi, và khi Koruto mở mắt ra lần nữa, thì trước mắt cậu chỉ còn là quyển sổ.

Quyển sổ có \(N\) trang, và mỗi trang là một hình vẽ có số hiệu \(a_i\). Tuy vậy, chẳng có hình vẽ nào là hoàn chỉnh. Mỗi trang chỉ vẽ được vài đường, vài góc, thậm chí vài nét của cô gái đó. Do đó, Koruto muốn chọn một số trang sao cho từ những trang đó, Koruto có thể vẽ lại được hình ảnh cô gái ấy một cách hoàn chỉnh nhất, tức là từ những số hiệu \(a_i\), mức độ rõ ràng được biểu hiện bằng \(d(a_i)\) với \(d(x)\) là số lượng ước số nguyên dương của \(x\). Hãy chọn một số trang (có thể chọn hết) sao cho số lượng ước số của tổng các số chọn được là nhiều nhất ?

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 30\)) — số lượng trang trong cuốn sổ.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^5\)) — giá trị của từng trang.

Output

• In ra một số nguyên duy nhất là số lượng ước số nguyên dương lớn nhất có thể đạt được của tổng các số trong một tập hợp con bất kỳ (chọn ít nhất một trang).

Example

3
2 3 6

4