测试数据来自 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