Description: 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 > 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$$$. Input Format: 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$$$. Output Format: For each test case, print the minimum total amount of ingredients needed to make a potion which passes the class, modulo $$$998\,244\,353$$$. Note: 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$$$.