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 lines, 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.

Constraints

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.

Example

Input
2
2 2
5 1

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.