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 \div 5 = 1~, and the HP of the third enemy is reduced to ~10 \div 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 \div 2 = 6~, and the HP of the third enemy is reduced to ~2 \div 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.