Problem E: PIPI的消消乐Ⅵ

Problem E: PIPI的消消乐Ⅵ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 89  Solved: 17
[Submit] [Status] [Web Board] [Creator:]

Description

一年过去,PIPI又来挑战新的消消乐游戏了。
游戏将会给出n个元素,PIPI需要进行若干次操作,对于每次操作,PIPI可以选择以下两种之一进行:
1.选择一个元素,使除了这个元素之外的所有元素乘以P,P为任意素数。
2.选择一个元素,使除了这个元素之外的所有元素除以P,P为任意素数。
只要使得所有元素一样,PIPI就能通关游戏。请问PIPI通关最少要进行多少次操作?

Input

第一行一个正整数n,n<=50000。
接下来n个正整数ai,ai<=50000。

Output

输出PIPI通关要进行的最少操作次数。

Sample Input

2
5 7

Sample Output

2