REF: COCI 2016/2017/Round #6 Task Sirni

Bi có một túi đựng đầy kẹo và có ~n~ tấm thẻ, mỗi tấm thẻ ghi một số nguyên dương ~p_i~ trên nó.

Bi rất thích ăn kẹo và nghĩ ra một cách rất hay như sau: Nếu liên kết hai thẻ với hai số nguyên ~p_a, p_b~ thì Bi sẽ ăn một số kẹo là min(p_a % p_b, p_b % p_a), ví dụ ~p_a = 2, p_b = 11~ thi Bi sẽ ăn ~1~ cái kẹo.

Bài toán đặt ra là hãy tìm cách liên kết hết các thẻ lại với nhau, mỗi thẻ có thể liên kết với bất kỳ thẻ nào khác sao cho số kẹo mà Bi ăn là ít nhất, vì Bi sợ bể dáng.

Input

Dòng thứ nhất là số nguyên dương ~n~ thỏa ~3 \le n \le 10^{5}~.

~n~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~p_i~ thỏa ~1 \le p_i \le 10^7~.

Output

In ra số kẹo ít nhất cần tìm.

Samples

Sample Input 1

4
2
6
3
11

Sample Output 1

1

Sample Input 2

3
4
9
15

Sample Output 2

4

Note

Ở testcase số ~1~, ta liên kết như sau: 1<-> 2, 2<-> 3, 1<->4