Let's call the roundness of the number the number of zeros to which it ends.

You have an array of n numbers. You need to choose a subset of exactly k numbers so that the roundness of the product of the selected numbers will be maximum possible.

Input

The first line contains two integer numbers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n).

The second line contains n space-separated integer numbers a1, a2, ..., an (1 ≤ ai ≤ 1018).

Output

Print maximal roundness of product of the chosen subset of length k.

Examples

Input

3 2
50 4 20


Output

3


Input

5 3
15 16 3 25 9


Output

3


Input

3 3
9 77 13


Output

0

Note

In the first example there are 3 subsets of 2 numbers. [50, 4] has product 200 with roundness 2, [4, 20] — product 80, roundness 1, [50, 20] — product 1000, roundness 3.

In the second example subset [15, 16, 25] has product 6000, roundness 3.

In the third example all subsets has product with roundness 0.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * https://codeforces.com/contest/837/problem/D
 * 3 2
 * 50 4 20 should output 3
 * 5 3
 * 15 16 3 25 9 should output 3
 */
public class RoundSubset {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer initial = new StringTokenizer(read.readLine());
        initial.nextToken();
        int subsetSize = Integer.parseInt(initial.nextToken());

        long[] nums = Arrays.stream(read.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        int[] twoPowers = Arrays.stream(nums).mapToInt(n -> powerNum(n, 2)).toArray();
        int[] fivePowers = Arrays.stream(nums).mapToInt(n -> powerNum(n, 5)).toArray();

        int maxFivePow = Arrays.stream(fivePowers).max().getAsInt() * subsetSize;
        int[][] maxTwoPos = new int[subsetSize + 1][maxFivePow + 1];
        for (int s = 0; s <= subsetSize; s++) {
            Arrays.fill(maxTwoPos[s], -1);
        }
        maxTwoPos[0][0] = 0;
        for (int i = 0; i < nums.length; i++) {
            // System.out.println("--------------------------------");
            for (int s = Math.min(subsetSize - 1, i + 1); s >= 0; s--) {
                for (int p = 0; p < maxFivePow; p++) {
                    if (maxTwoPos[s][p] == -1) {
                        continue;
                    }
                    maxTwoPos[s + 1][p + fivePowers[i]] = Math.max(
                            maxTwoPos[s + 1][p + fivePowers[i]],
                            maxTwoPos[s][p] + twoPowers[i]
                    );
                }
            }
            // for (var asdf : maxTwoPos) System.out.println(Arrays.toString(asdf));
        }

        int roundest = 0;
        for (int p = 1; p <= maxFivePow; p++) {
            roundest = Math.max(roundest, Math.min(p, maxTwoPos[subsetSize][p]));
        }
        System.out.println(roundest);
    }

    // returns how many times k goes into n
    private static int powerNum(long n, int k) {
        int c = 0;
        while (n % k == 0) {
            c++;
            n /= k;
        }
        return c;
    }
}
