Mike is playing a strange video game!

There are $N$ enemies that Mike is able to attack. The $i$-th enemy initially has an HP of $h_i$.

In one attack, Mike can select a subset of the $N$ enemies containing at least $K$ enemies, and a positive integer $x$ such that $x>1$. He must choose the subset and the value of $x$ such that $x$ is a factor of the HPs of all enemies in the subset. Then, the HPs of all enemies in the subset will be divided by $x$.

Mike wants to attack the enemies as many times as possible. Can you help Mike find the maximum number of times he can perform an attack?

Constraints

$2\le K\le N\le 3\times {10}^6$

$1\le h_i\le {10}^6$

Subtask 1 [20%]

$2\le N\le 1000$

$1\le h_i\le 1000$

$K=2$

Subtask 2 [40%]

$K=2$

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains a two space separated integer containing the values of $N$ and $K$.

The next line contains $N$ space separated integers, $h_1,h_2,\dots ,h_N$, representing the initial HPs of the enemies.

Output Specification

On a single line, print the maximum possible number of attacks which can be performed.

Sample Input

3 2
5 12 10

Sample Output

2

Explanation

For the first attack, Mike can choose the first and third enemies in his subset, and choose $x=5$. The HP of the first enemy is reduced to $5÷5=1$, and the HP of the third enemy is reduced to $10÷5=2$.

For the second attack, Mike can choose the second and third enemies in his subset, and choose $x=2$. The HP of the second enemy is reduced to $12÷2=6$, and the HP of the third enemy is reduced to $2÷2=1$.

At this point, Mike cannot perform any more attacks. It can be shown that $2$ is the maximum possible number of attacks which Mike can perform.