One day during the fight between good and evil, Meganath used his Brahmastra on Lakshman. As nothing could stop a Brahmastra so Lakshman got badly injured and would die the next day. Sushen, the doctor, was called to cure Lakshman. Sushen explained following thing.

He said " Brahmastra consists of an array of integers and to find an antidote for it you have to find the sum of number of square free divisors of each number in the array ". Formally you will be given an array A of positive integers and for each element A[i] find it's number of square free divisors, d[i]. Finally you have to compute the sum of all d[i]'s.

Input:

On the first line there will be N, denoting the number of integers in the array.

On the next line there will be N positive integers, A[i].

Output:

Output consist of one line denoting the value of the required sum.

Constraint:

0 < N <=2000000 (2*10^6)

0 < A[i] <= 10000000 (10^7)

Note: Use scanf() , printf() for I/O