Mr. F has n positive integers, a_1, a_2, …, a_n.

He thinks the greatest common divisor of these integers is too small. So he wants to enlarge it by removing some of the integers.

But this problem is too simple for him, so he does not want to do it by himself. If you help him, he will give you some scores in reward.

Your task is to calculate the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

Input

The first line contains an integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of integers Mr. F has.

The second line contains n integers, a_1, a_2, …, a_n (1 ≤ a_i ≤ 1.5 ⋅ 10^7).

Output

Print an integer — the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

You should not remove all of the integers.

If there is no solution, print «-1» (without quotes).

Examples

Input

3
1 2 4


Output

1

Input

4
6 9 15 30


Output

2

Input

3
1 1 1


Output

-1

Note

In the first example, the greatest common divisor is 1 in the beginning. You can remove 1 so that the greatest common divisor is enlarged to 2. The answer is 1.

In the second example, the greatest common divisor is 3 in the beginning. You can remove 6 and 9 so that the greatest common divisor is enlarged to 15. There is no solution which removes only one integer. So the answer is 2.

In the third example, there is no solution to enlarge the greatest common divisor. So the answer is -1.
/*input
3
1 1 1

*/

import java.util.*;
import java.io.*;
import java.math.*;
public class CF511C
{
    static final int MAXN = 15000005; 
       
    // stores smallest prime factor for every number 
    static int spf[] = new int[MAXN]; 
	public static void main(String[] args) throws Exception
	{
		StringBuffer sb = new StringBuffer();
		Bolt sc = new Bolt(System.in);	
		int n=sc.nextInt();
        int max=15000005;
        int[] arr = new int[n];
        int hcf=0;
        sieve();
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
            hcf=gcd(hcf,arr[i]);
        }
        int[] freq=new int[15000005];
        int maxi=1;


        for(int i=0;i<n;i++)
        {
            ArrayList<Integer> al = getFactorization(arr[i]/hcf);
            // int[] f=new int[15000005];
        HashSet<Integer> se=new HashSet<Integer>();
        int len=al.size();
        for(int j=0;j<len;j++)
        {
            int x=al.get(j);
            se.add(x);
            // f[x]=1;
        }
        for(Integer num : se)
        {
            freq[num]++;
            if(num>maxi)
                maxi=num;
        }
        // while(se.hasNext())
        // {
        //     int x=se.next();
        //     freq[x]++;
        //     if(x>maxi)
        //         maxi=x;
        // }
        // for(int j=0;j<len;j++)
        // {
        //     int x=al.get(j);
        //     System.out.println(x);
        //     freq[x]++;
        //     if(x>maxi)
        //         maxi=x;
        // }
        }


        int ans=Integer.MAX_VALUE;
        int count=ans;
        // System.out.println(freq[2]);
        for(int i=1;i<=maxi;i++)
        {
            if(freq[i]==0)
                continue;
            if((n-freq[i])<=ans)
            {
                
                ans = n-freq[i];
                
            }
        }

        if(ans!=count)
        {
            System.out.println(ans);
        }
        else
            System.out.println(-1);

    }


    static int gcd(int a, int b) 
    { 
      if (b == 0) 
        return a; 
      return gcd(b, a % b);  
    } 

       
    // Calculating SPF (Smallest Prime Factor) for every 
    // number till MAXN. 
    // Time Complexity : O(nloglogn) 
    static void sieve() 
    { 
        spf[1] = 1; 
        for (int i=2; i<MAXN; i++) 
       
            // marking smallest prime factor for every 
            // number to be itself. 
            spf[i] = i; 
       
        // separately marking spf for every even 
        // number as 2 
        for (int i=4; i<MAXN; i+=2) 
            spf[i] = 2; 
       
        for (int i=3; i*i<MAXN; i++) 
        { 
            // checking if i is prime 
            if (spf[i] == i) 
            { 
                // marking SPF for all numbers divisible by i 
                for (int j=i*i; j<MAXN; j+=i) 
       
                    // marking spf[j] if it is not  
                    // previously marked 
                    if (spf[j]==j) 
                        spf[j] = i; 
            } 
        } 
    } 
       
    // A O(log n) function returning primefactorization 
    // by dividing by smallest prime factor at every step 
    static ArrayList<Integer> getFactorization(int x) 
    { 
        ArrayList<Integer> ret = new ArrayList<Integer>(); 
        while (x != 1) 
        { 
            ret.add(spf[x]); 
            x = x / spf[x]; 
        } 
        return ret; 
    } 

}

class Bolt
{
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
 
        public Bolt(InputStream stream) {
            this.stream = stream;
        }
 
        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int peek() {
            if (numChars == -1)
                return -1;
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    return -1;
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar];
        }
 
        public void skip(int x) {
            while (x-- > 0)
                read();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
        public String nextString() {
            return next();
        }
 
        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
 
            return res.toString();
        }
 
        public String nextLine() {
            StringBuffer buf = new StringBuffer();
            int c = read();
            while (c != '\n' && c != -1) {
                if (c != '\r')
                    buf.appendCodePoint(c);
                c = read();
            }
            return buf.toString();
        }
 
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
 
        public boolean hasNext() {
            int value;
            while (isSpaceChar(value = peek()) && value != -1)
                read();
            return value != -1;
        }
 
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
}