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.util.Scanner;


public class Main {
	
	private static int[][] dp = new int[300][300 * 30];
	private static int[] cnt2 = new int[202];
	private static int[] cnt5 = new int[202];
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int i , j , n , k;
		n = scan.nextInt();
		k = scan.nextInt();
		for (i = 0;i < n;i ++) {
			long value = scan.nextLong();
			while (value % 2 == 0) {
				value /= 2;
				cnt2[i] ++;
			}
			while (value % 5 == 0) {
				value /= 5;
				cnt5[i] ++;
			}
		}

		int ans = 0;
		for (i = 0;i < 300;i ++) {
			for (j = 0;j < 30 * 300;j ++) {
				dp[i][j] = - 1;
			}
		}
		dp[0][0] = 0;
		dp[1][cnt5[0]] = cnt2[0];
		for (i = 1;i < n;i ++) {
			for (j = k - 1;j >= 0;j --) {
				for (int pos = 30 * 300 - 1;pos >= 0;pos --) {
					if (pos + cnt5[i] < 30 * 300 && dp[j][pos] >= 0) {
						int next5 = pos + cnt5[i];
						int next2 = dp[j][pos] + cnt2[i];
						if (next2 > dp[j + 1][next5]) {
							dp[j + 1][next5] = next2;
						}
					}
				}
			}
		}
		for (i = 0;i < 30 * 300;i ++) {
			if (dp[k][i] >= 0) {
				int temp = Math.min(i , dp[k][i]);
				if (temp > ans) {
					ans = temp;
				}
			}
		}
		System.out.println(ans);
		
	}
	
}

















