CF1654D.Potion Brewing Class

Alice's potion making professor gave the following assignment to his students: brew a potion using $n$ ingredients, such that the proportion of ingredient $i$ in the final potion is $r_i \gt 0$ (and $r_1 + r_2 + \cdots + r_n = 1$).

He forgot the recipe, and now all he remembers is a set of $n-1$ facts of the form, "ingredients $i$ and $j$ should have a ratio of $x$ to $y$" (i.e., if $a_i$ and $a_j$ are the amounts of ingredient $i$ and $j$ in the potion respectively, then it must hold $a_i/a_j = x/y$), where $x$ and $y$ are positive integers. However, it is guaranteed that the set of facts he remembers is sufficient to uniquely determine the original values $r_i$.

He decided that he will allow the students to pass the class as long as they submit a potion which satisfies all of the $n-1$ requirements (there may be many such satisfactory potions), and contains a positive integer amount of each ingredient.

Find the minimum total amount of ingredients needed to make a potion which passes the class. As the result can be very large, you should print the answer modulo $998\,244\,353$.

爱丽丝的魔药学教授给学生们布置了如下作业：使用 $n$ 种原料配制一种魔药，使得第 $i$ 种原料在最终魔药中所占比例为 $r_i \gt 0$（且满足 $r_1 + r_2 + \cdots + r_n = 1$）。

他遗忘了原始配方，如今仅记得一组共 $n-1$ 条事实，每条形如：“原料 $i$ 与原料 $j$ 的用量之比应为 $x : y$”（即若魔药中原料 $i$ 与原料 $j$ 的用量分别为 $a_i$ 和 $a_j$，则必须满足 $a_i/a_j = x/y$），其中 $x$ 和 $y$ 均为正整数。但题目保证他所记住的这组事实足以唯一确定原始比例值 $r_i$。

他决定：只要学生提交的魔药满足全部 $n-1$ 条约束条件（满足条件的魔药可能有多个），且每种原料的用量均为正整数，则视为通过课程。

请找出满足上述要求的魔药所需的最小总原料用量。由于答案可能非常大，请将结果对 $998\,244\,353$ 取模后输出。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).

Each of the next $n-1$ lines contains four integers $i, j, x, y$ ($1 \le i, j \le n$, $i\not=j$, $1\le x, y \le n$) — ingredients $i$ and $j$ should have a ratio of $x$ to $y$. It is guaranteed that the set of facts is sufficient to uniquely determine the original values $r_i$.

It is also guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。

接下来的 $n-1$ 行中，每行包含四个整数 $i, j, x, y$（$1 \le i, j \le n$，$i \neq j$，$1 \le x, y \le n$）—— 表示原料 $i$ 与原料 $j$ 的比例应为 $x : y$。题目保证所给条件足以唯一确定原始值 $r_i$。

同时保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print the minimum total amount of ingredients needed to make a potion which passes the class, modulo $998\,244\,353$.

对于每个测试用例，输出制作一剂能通过课程的药水所需的最少总原料量，对 $998\,244\,353$ 取模。

In the first test case, the minimum total amount of ingredients is $69$. In fact, the amounts of ingredients $1, 2, 3, 4$ of a valid potion are $16, 12, 9, 32$, respectively. The potion is valid because

• Ingredients $3$ and $2$ have a ratio of $9 : 12 = 3 : 4$;
• Ingredients $1$ and $2$ have a ratio of $16 : 12 = 4 : 3$;
• Ingredients $1$ and $4$ have a ratio of $16 : 32 = 2 : 4$.

In the second test case, the amounts of ingredients $1, 2, 3, 4, 5, 6, 7, 8$ in the potion that minimizes the total amount of ingredients are $60, 60, 24, 48, 32, 60, 45, 30$.

在第一个测试用例中，所需原料的最小总量为 $69$。事实上，一种合法药水所需的原料 $1, 2, 3, 4$ 的量分别为 $16, 12, 9, 32$。该药水是合法的，因为：

• 原料 $3$ 与原料 $2$ 的比例为 $9 : 12 = 3 : 4$；
• 原料 $1$ 与原料 $2$ 的比例为 $16 : 12 = 4 : 3$；
• 原料 $1$ 与原料 $4$ 的比例为 $16 : 32 = 2 : 4$。

在第二个测试用例中，使原料总用量最小的药水中，原料 $1, 2, 3, 4, 5, 6, 7, 8$ 的用量分别为 $60, 60, 24, 48, 32, 60, 45, 30$。