An đang chơi trò chơi Chiến tranh giữa các vì sao. Trong trò chơi, nhân vật của An cần phải thu được càng nhiều sức mạnh càng tốt từ các vì sao trong vũ trụ.

Có ~n~ vì sao được đánh số từ ~1~ đến ~n~ mà nhân vật của An có thể sẽ đi qua. Để không làm tổn hại đến sự toàn vẹn của vũ sao, nhân vật không thể quay ngược, nghĩa là nếu nhân vật đã đi từ vì sao thứ nhất đến vì sao thứ tư, thì nhân vật không thể đi đến vì sao thứ hai hoặc thứ ba, nhân vật phải tiếp tục đi về phía trước. Tổng quát, nếu nhân vật đang ở vì sao ~i~ thì nhân vật chỉ có thể đi đến vì sao ~j~ với ~j ≥ i~.

Với mỗi hành tinh ~i~ có một tham số ~a_i~. Khi nhân vật của An đi từ hành tinh ~i~ đến hành tinh ~j~, nó sẽ nhận thêm một sức mạnh ~gcd (a_i, a_j)~, trong đó ~gcd (a_i, a_j)~ là ước chung lớn nhất của ~a_i~ và ~a_j~. Lúc bắt đầu, sức mạnh của An có ~1~ đơn vị sức mạnh và xuất phát từ vì sao ~1~. Mục tiêu của An là đưa nhân vật đến vì sao ~n~ với tổng sức mạnh lớn nhất. Cụ thể là tìm một dãy các chỉ số ~i_1 = 1, i_2 < ... < i_k = n~, sao cho tổng sau lớn nhất:

$$1 + gcd(a_{i_1}, a_{i_2}) + gcd(a_{i_2}, a_{i_3}) + ... + gcd(a_{i_{k-1}}, a_{i_k})$$

Bạn hãy giúp An tính tổng sức mạnh lớn nhất mà nhân vật của anh ta có thể nhận được.

INPUT

Dòng đầu tiên chứa số nguyên ~n~ (~1 ≤ n ≤ 2 \times 10^5~) là số vì sao.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ 2 \times 10^5 + 3~) là các tham số của các vì sao.

OUTPUT

Một số nguyên là tổng sức mạnh lớn nhất mà nhân vật của An có thể nhận được.

SAMPLE INPUT 1

4
5 1 1 5

SAMPLE OUTPUT 1

6

Trong ví dụ đầu tiên, An sẽ di chuyển nhân vật từ vì sao ~1~ đến vì sao ~4~. Chú ý rằng, ban đầu nhân vật có ~1~ đơn vị sức mạnh. Tổng sức mạnh của nhân vật sẽ là: ~1 + gcd (5, 5) = 6~.

SAMPLE INPUT 2

5
6 4 15 9 10

SAMPLE OUTPUT 2

9

Trong ví dụ thứ hai, An sẽ di chuyển nhân vật từ vì sao ~1~ đến vì sao ~3~, rồi đến vì sao ~5~. Tổng sức mạnh của nhân vật sẽ là: ~1 + gcd (6,15) + gcd (15,10) = 9~.

SUBTASKS

• Có ~20 \%~ số test thỏa mãn ~n \le 20~.
• Có ~20 \%~ số test thỏa mãn ~n \le 1000~.
• Có ~20 \%~ số test thỏa mãn ~a_i~ là các số nguyên tố.
• Có ~20 \%~ số test thỏa mãn ~n \le 2 \times 10^4~ và ~a_i \le 100~.
• Có ~20 \%~ số test không có ràng buộc gì thêm.