SOD means the Sum of Divisors. To be more specific, if we sum up all the divisors of a number then the result is called SOD of the number.

Here you have to implement the same task i.e. you have to calculate the SOD of a number.

Let’s say the number is n.

But the input format will be a bit different. I will not give you the number directly. I will give you some information regarding the number where you can calculate the number.

The information will be the number of prime factors of n and how many times this prime factor will occur in n.

For example, if I give you two pairs like (2, 2) and (3, 1), then the actual number will be

                                                                              n = 2² * 3¹

And the answer for the given two pairs of input will be 28 as the actual number n = 12 and the divisors of 12 are 1, 2, 3, 4, 6, 12. 

Input :

In the first line, you will be given an integer q.

In the next line, you will be given q pairs of integers of the form (p_i, cnt_i ) where p_i is a prime and cnt_i is the number of times this prime occurs in the actual number, n.

Constraint:

1 <= q <= 4

1 <= p_i <= 10

1 <= cnt_i <= 5

It is guaranteed that that p_i will be a prime number.

Output:

Print the SOD, the result of the given number, n.

Sample Input

2

2 2

5 1

Sample Output

42

Explanation:

n = 2² * 5¹ = 20. So the divisors of 20 are 1, 2, 4, 5, 10, and 20 and after summing up every divisor of 20 the result is 42.