Nguồn: Free Contest

Cho dãy số ~a_1, a_2, ..., a_N~ gồm ~N~ số nguyên dương. Gọi ~X~ là ước chung lớn nhất của dãy số. Lucas muốn bỏ đi ít số nhất sao cho ước chung lớn nhất của dãy sau khi bỏ lớn hơn ~X~. Bạn hãy giúp Lucas tìm ra số lượng số bỏ đi ít nhất. Nếu không có cách nào hãy xuất ~-1~.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \le N \le 10^5)~.
• Dòng tiếp theo chứa ~N~ số nguyên. Số nguyên thứ ~i~ là ~a_i~ ~(1 \le a_i \le 5.10^6)~.

Output

• Một số nguyên duy nhất là đáp án của bài toán.

Samples

Sample Input 1

3
1 2 4

Sample Output 1

1

Clarification

Ước chung lớn nhất của dãy số ban đầu là ~X = 1~. Ta cần bỏ một số là số ở vị trí đầu tiên thì ước chung lớn nhất của dãy còn lại là ~2~ (lớn hơn ~X~).