Manasa is a student in the department of Mathematics. She is pretty good at doing calculations involving small numbers, but large numbers scare her. So she wants you to help her in the following calculations.

Given two numbers in the following manner:

( is a prime number, and all the 's are distinct)

She wants you to calculate for her, where is the sum of for all pairs of numbers where , and . In other words:

As the value of can be very large, she wants you to print .

Input Format
The first line contains an integer , the number of prime factors.
Each of the next lines contains three numbers: , and .

Output Format
Print the value of .

Constraints

Sample Input

2
2 1 2 
3 1 2

Sample Output

72

Explanation

We have and . There are two pairs of integers with equal to and equal to , and such that . These are and :

• and
• and

Hence,