Problem: Given are a sequence A= {a_1,a_2,......a_N} of N positive even numbers, and an integer M.

Let a semi-common multiple of A be a positive integer X that satisfies the following condition for every k (1 \leq k \leq N):

* There exists a non-negative integer p such that X= a_k \times (p+0.5).



Find the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Constraints

* 1 \leq N \leq 10^5
* 1 \leq M \leq 10^9
* 2 \leq a_i \leq 10^9
* a_i is an even number.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M
a_1 a_2 ... a_N


Output

Print the number of semi-common multiples of A among the integers between 1 and M (inclusive).

Examples

Input

2 50
6 10


Output

2


Input

3 100
14 22 40


Output

0


Input

5 1000000000
6 6 2 6 2


Output

166666667

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = in.nextIntArray(n);
        a = Arrays.stream(a).map(i -> i / 2).toArray();

        Map<Long, Integer> lcmFact = new HashMap<>();
        for (int i : a) {
            PrimeFact pf = new PrimeFact(i);
            pf.factorization.forEach((p, c) -> lcmFact.put(p, Math.max(lcmFact.getOrDefault(p, 0), c)));
        }

        long lcm = 1;
        for (Map.Entry<Long, Integer> e : lcmFact.entrySet()) {
            for (int i = 0; i < e.getValue(); i++) {
                lcm *= e.getKey();
                if (lcm > m) {
                    out.println("0");
                    return;
                }
            }
        }

        for (int i : a) {
            if ((lcm / i) % 2 == 0) {
                out.println("0");
                return;
            }
        }

        int ans = (int) Math.max(0, (m / lcm + 1) / 2);
        out.println(ans);
    }

    private static class PrimeFact {
        private final long orig;
        private Map<Long, Integer> factorization;

        PrimeFact(long num) {
            orig = num;
            factorization = factorize(num);
        }

        PrimeFact(int num) {
            orig = num;
            factorization = factorize(num);
        }

        /**
         * Returns a list of divisors, including.
         * @return List of divisors.
         */
        public List<Long> divisors() {
            return getDivisors(this.factorization);
        }

        /**
         * Checks if the internal factorization map contains only one value,
         * and it is num itself & corresponding power equals 1.
         * @return {@code true} if prime.
         */
        boolean isPrime() {
            return this.factorization.size() == 1
                    && this.factorization.entrySet().stream().findFirst().get().getValue() == 1;
        }

        /**
         * Returns a factorization map inside.
         */
        public Map<Long, Integer> getFactorization() {
            return factorization;
        }
    }

    private static Map<Long, Integer> factorize(final long num) {
        Map<Long, Integer> fact;

        if (num == 1L) return new HashMap<>();

        long sqrt = (long) Math.floor(Math.sqrt(num));
        if (sqrt > primes.getLast()) {
            generatePrimes(sqrt);
        }

        for (long p : primes) {
            if (p > sqrt) break;
            if (num % p == 0) {
                fact = factorize(num / p);
                if (fact.containsKey(p)) fact.put(p, fact.get(p) + 1);
                else fact.put(p, 1);
                return fact;
            }
        }

        // given num is a prime number
        fact = new HashMap<>();
        fact.put(num, 1);
        return fact;
    }

    private static LinkedList<Long> primes;

    static {
        primes = new LinkedList<>();
        primes.add(2L);
    }

    /**
     * Generates primes and stores it into static `primes` field.
     * Stops if the last generated prime is larger than the given `min`.
     * @param min Minimum number. Usually sqrt of the number that we want to factorize.
     */
    private static void generatePrimes(long min) {
        long p = primes.getLast() + 1;
        while (true) {
            if (isPrime(p)) {
                primes.add(p);
                if (p > min) {
                    return;
                }
            }
            p++;
        }
    }

    /**
     * Checks if the number is a prime using the current `primes` cache.
     * Stops when the next prime is larger than floor(sqrt(num)).
     * @param num Number to check.
     * @return {@code true} if num is prime.
     */
    private static boolean isPrime(long num) {
        int sqrt = (int) Math.floor(Math.sqrt(num));

        for (long p : primes) {
            if (p > sqrt) break;
            if (num % p == 0) return false;
        }

        return true;
    }

    // ------------------------
    // Get Divisors List
    // ------------------------

    /**
     * Returns a list of divisors, including 1 and number itself.
     * @param fact Factorization map.
     * @return List of divisors.
     */
    private static List<Long> getDivisors(Map<Long, Integer> fact) {
        List<Long> ret = new ArrayList<>();
        if (fact.isEmpty()) {
            ret.add(1L);
            return ret;
        }

        for (Map.Entry<Long, Integer> e : fact.entrySet()) {
            Map<Long, Integer> copy = clone(fact);
            copy.remove(e.getKey());
            List<Long> divs = getDivisors(copy);
            for (long div : divs) {
                for (int i = 0; i <= e.getValue(); i++) {
                    ret.add(div * (long) Math.pow(e.getKey(), i));
                }
            }
            break;
        }
        return ret;
    }

    /**
     * Clones map h into a new HashMap.
     * @param m Map to clone.
     * @return Cloned map.
     */
    private static Map<Long, Integer> clone(Map<Long, Integer> m) {
        Map<Long, Integer> ret = new HashMap<>();
        for (Map.Entry<Long, Integer> e : m.entrySet()) {
            ret.put(e.getKey(), e.getValue());
        }
        return ret;
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}