Mobiles are widely loved as kinetic art pieces. The IOI Japan Committee decided to create a mobile to promote JOI. The JOI promotional mobile is constructed as follows using $3$ types of elements: rods, strings, and weights.

• One end of each rod is painted blue, and the other end is painted red.
• Each rod is suspended by a string at $1$ point other than its two ends as a fulcrum.
• Both the length from the fulcrum to the red end and the length from the fulcrum to the blue end are positive integers.
• At each of the two ends of a rod, either a weight or another rod is suspended by a string.
• Each weight is suspended by a string from one end of some rod.
• Nothing is suspended from a weight.
• The weight of each weight is a positive integer.
• Exactly $1$ of the strings has one end tied to the fulcrum of some rod in order to suspend that rod, and its other end is not tied to any other constituent element. Every other string satisfies one of the following:
  • It connects an end of some rod and the fulcrum of some rod.
  • It connects an end of some rod and some weight.

However, every rod must be balanced. Since the weights of the rods and strings are light enough to be negligible, solve the problem assuming that the weights of all rods and strings are $0$. In other words, for each rod, consider the rod to be balanced when:

(total weight of weights suspended below the red end of the rod) $\times$ (length from the fulcrum of the rod to the red end) $=$ (total weight of weights suspended below the blue end of the rod) $\times$ (length from the fulcrum of the rod to the blue end)

Caption for the 4 diagrams above — Top-left: Example of a simple mobile; Top-right: Example that is not a mobile because it is not balanced; Bottom-left: Example of a mobile; Bottom-right: Example that is not a mobile.

How rods of what lengths are connected to construct the mobile has already been decided, but the weights of the weights have not yet been decided. Since a lighter mobile is easier to hang, we want to make a mobile that is as light as possible. As described above, write a program that finds how to attach weights so as to minimize the total weight of the mobile while keeping every rod balanced, and outputs the total weight of the mobile in that case. The program is given the following information regarding the structure of the mobile:

• The number of rods $n$
• Information for each rod (rod numbers are from $1$ to $n$):
  • The ratio of the length from the fulcrum to the red end and the length from the fulcrum to the blue end
  • The rod number suspended from the red end ($0$ if a weight is suspended)
  • The rod number suspended from the blue end ($0$ if a weight is suspended)

Caption for the 2 diagrams above — Left (Rod number $1$): The lightest mobile with this structure; Right (Rod number $1$): A mobile that is not the lightest.

Input

The $1$-st line contains the number of rods $n$ used in the mobile. The following $n$ lines ($1 \le n \le 100$) contain the data for each rod. The ($i + 1$)-th line ($1 \le i \le n$) contains $4$ integers $p, q, r, b$ separated by spaces, indicating that for rod $i$, the ratio of the length from the fulcrum to the red end and the length from the fulcrum to the blue end is $p : q$, the rod number suspended from the red end is $r$, and the rod number suspended from the blue end is $b$. Here, rod number $0$ indicates that a weight is suspended. Also, in every input, if $w$ is the minimum value of the weight of the mobile and $L$ is the maximum value of the positive integers used to represent the ratios in the input, then $w L < 2^{31}$ is satisfied.

Output

The output consists of $1$ line, outputting the weight of the mobile.

Sample Input and Output

Sample Input 1

1
6 9 0 0

Sample Output 1

5

Sample Input 2

4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0

Sample Output 2

40