最軽量のモビール

問題

モビールは動く芸術品として広く親しまれている.IOI 日本委員会では,JOI を広報するためにモビールを作成することになった.JOI 広報用モビールは,棒,紐(ひも),錘(おもり)の 3 種類の要素を用いて,次のように構成される.

ただし,どの棒においても,バランスが取れている必要がある.棒と紐の重さは無視できるほど軽いので,棒と紐の重さは全て 0 であるとみなして解答せよ.つまり,それぞれの棒について,

(その棒の赤の端より下につるされている錘の重さの総計) × (その棒の支点から赤の端までの長さ) = (その棒の青の端より下につるされている錘の重さの総計) × (その棒の支点から青の端までの長さ)

であるとき,その棒はバランスが取れているとせよ.


どのような長さの棒をどのように結びモビールを構成するかは既に決まっているのだが,錘の重さがまだ決まっていない.モビールは軽い方がつりやすいため, なるべく軽いモビールを作りたい.前述したようにどの棒もバランスを取りながら, モビールの総重量を最小にするような錘の付け方を求め, そのときのモビールの総重量を出力するプログラムを作れ. プログラムには以下のモビールの構成に関する情報が与えられる.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロ１つを含む行で終了する．

1 行目にはモビールに使われている棒の本数 n が書かれている.続く n è¡Œ (1 ≤ n ≤ 100) には,各々の棒のデータが書かれている.i + 1 行目 (1 ≤ i ≤ n) には,4 つの整数 p, q, r, b が空白を区切りとして書かれており,棒 i において,支点から赤の端までの長さと支点から青の端までの比が p : q であり,赤の端につるされる棒の番号が r であり,青の端につるされる棒の番号が b であることを表している.ただし,棒番号 0 は錘がつるされることを表している.また,どの入力においても,モビールの重量の最小値を w とし,入力中で比を表すのに用いられる正整数の最大値を L とすると,wL < 231 を満たす.

データセットの数は 15 を超えない．

出力

データセットごとにモビールの重量を１行に出力する．

入出力例

入力例

1
6 9 0 0
4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0
0

出力例

5
40

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。