测试数据来自 AOCode/1053

P1053 New Operation Defined

Problem Statement

AO and AO's npy's math teacher, YYQ, defined a new operation.

• If \(x\) is a prime number, then \(f(x)=1\)
• If \(a\) and \(b\) are two integers that are greater than 1, then \(f(a \times b)= b \times f(a) +a \times f(b) \)

YYQ wrote a huge number, \(y\) on the blackboard. It's so huge that he had to write it as a product of many prime numbers. He wanted AO's npy to calculate \(f(y)\). Unfortunately, she wasn't able to do that. To save his npy, AO raised up his hand.

Input

The first line contains \(n\), the number of prime numbers.
The next line contains \(n\) integers, \(a_1, a_2, a_3, ......, a_n\) the prime numbers, whose product is \(y\)

Output

One integer, \(f(y)\).

Sample

Input 1

4
2 2 2 3

Output 1

44

For this case, \( f(2 \times 2 \times 2 \times 3) = f(24) = 4 \times f(6) + 6 \times f(4) = 4 \times (2 \times f(3) + 3 \times f(2)) + 6 \times (2 \times f(2) + 2 \times f(2)) = 4 \times 5 + 6 \times 4 = 20 + 24 = 44 \)

Constraints

• For every \( 1 \le i \le n\) , \( 2 \le a_i \le 10^3 \)
• \( 1 \le n \le 2000 \)

Source?

Times Maths Newspaper (bushi